题目：有10个任意的正整数，将其分为两组A和B，要求组A中每个数据的和与组B中每个数据的和之差的...
题目：有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小的数了。
版权声明
本文仅代表作者观点，不代表百度立场。
本文系作者授权百度百家发表，未经许可，不得转载。
