經典算法詳解（8）數的分組

題目：有10個任意的正整數，将其分為兩組A和B，要求組A中每個資料的和與組B中每個資料的和之差的絕對值最小。請設計算法實作數的分組（找出一個答案即可）。

C++版本：

1 #include<iostream>
 2 
 3 using namespace std;
 4 
 5 void get_groupAB(int arr[]) {
 6     int sum_a, sum_b;
 7     int index, difference=0;
 8     int i,i_copy;
 9     //數組所有的元素求和給difference賦初值
10     for ( i = 0; i < 10; i++) {
11         difference += arr[i];
12     }
13     //從0000000000到1111111111，尾數為零時，對應的數組元素劃分給a數組，否則劃分給b數組
14     for ( i = 0; i < 0x3FF; i++) {            
15         sum_a = 0, sum_b = 0;
16         i_copy=i;
17         for (int j = 0; j < 10; j++) {
18             if ((i_copy & 1) == 0) {
19                 sum_a += arr[9 - j];
20             }
21             else {
22                 sum_b += arr[9 - j];
23             }
24             i_copy >>= 1;
25         }
26         if (difference > abs(sum_a - sum_b)) {
27             difference = abs(sum_a - sum_b);
28             index = i;            //存儲最小值對應的索引
29         }
30         if (difference == 0) {
31             break;
32         }
33     }
34     //存儲分組
35     int sub_a[10], sub_b[10];
36     int count_a=0, count_b=0;
37     for (i = 0; i < 10; i++) {
38         if ((index & 1) == 0) {
39             sub_a[count_a] = arr[9 - i];
40             count_a++;
41         }
42         else {
43             sub_b[count_b] = arr[9 - i];
44             count_b++;
45         }
46         index >>= 1;
47     }
48     //輸出顯示部分
49     cout << "group A:" << endl;
50     for (i = 0; i < count_a; i++) {
51         cout << sub_a[i] << endl;
52     }
53     cout << "group B:" << endl;
54     for (i = 0; i < count_b; i++) {
55         cout << sub_b[i] << endl;
56     }
57     cout << "difference:" << difference << endl;
58 }
59 
60 int main(int argc, char *argv[]) {
61 
62     int arr[10];
63     int i=0;
64     while (i < 10) {
65         cin >> arr[i];
66         i++;
67     }
68     get_groupAB(arr);
69     getchar();
70     getchar();
71     return 0;
72 }      

思路：可以用一個10位的二進制數表示，對應位置為零時，分給一個組，為1時分給另外一個組；任何一個數都可以分給組A或者組B兩種情況，故總的情況共有2^10，即1024種，其中不能全給A，也不能全給B，是以總共1024-2=1022種情況，進行枚舉即可。另外如果出現內插補點為0時可以馬上終止循環，因為不可能出現比0小的數了。