今天又看見了這個題目，好像上次是李災跟我說騰訊面他的時候問了這個問題的。想了半天，在網上也看了半天，發現一個不錯的算法，先帖出來：^ ^

 /*    有兩個數組a,b，大小都為n,數組元素的值任意整形數，無序；    要求：通過交換a,b中的元素，使[數組a元素的和]與[數組b元素的和]之間的差最小。*//*    求解思路：    當前數組a和數組b的和之差為    A = sum(a) - sum(b)    a的第i個元素和b的第j個元素交換后，a和b的和之差為    A' = sum(a) - a[i] + b[j] - （sum(b) - b[j] + a[i])           = sum(a) - sum(b) - 2 (a[i] - b[j])           = A - 2 (a[i] - b[j])    設x = a[i] - b[j]    |A| - |A'| = |A| - |A-2x|    假設A > 0,    當x 在 (0,A)之間時，做這樣的交換才能使得交換后的a和b的和之差變小，x越接近A/2效果越好,    如果找不到在(0,A)之間的x，則當前的a和b就是答案。    所以算法大概如下：    在a和b中尋找使得x在(0,A)之間并且最接近A/2的i和j，交換相應的i和j元素，重新計算A后，重復前面的步驟直至找不到(0,A)之間的x為止。*/

 把算法大概實現了一下，程序如下：

  1  int  test( float  a[],  float  b[],  int  n)  2  {  3       float  sumA, sumB;  // sumA為數組a總和，sumB為數組b總和   4       float  sum_diff, num_diff;  // sum_diff為a,b總和差， num_diff為a,b中各選的兩個數之差   5       float  temp1, temp2;     // temp1為 每輪sum_diff/2， temp2為每輪所選兩個數之差于temp1最接近的那個   6       int  i, j;  7       float  temp;  // 用于對調a,b間數   8       int  tempi, tempj;     // 每輪所選兩個數之差于temp1最接近的那組數   9      unsigned  int  flag_sum  =   0 , flag_num  =   0 ;   // flag_sum為1， sumA大于sumB; flag_num為1, 此輪存在兩個數之差小于sum_diff  10   11   12           13   14       while ( 1 ){ 15   16           // 算出a,b數組和  17          sumA  =   0 ; 18          sumB  =   0 ; 19           for (i = 0 ;i  <  n;i ++ ) 20          { 21              sumA  +=  a[i]; 22              sumB  +=  b[i]; 23          } 24   25           if (sumA  >=  sumB){ 26              sum_diff  =  sumA  -  sumB; 27              flag_sum  =   1 ; 28          } 29           else  30              sum_diff  =  sumB  -  sumA;     31       32          temp1  =  sum_diff / 2 ; 33          temp2  =  temp1; 34          tempi  =   0 ; 35          tempj  =   0 ;     36       37           // 找出a,b間差值最接近sum_diff/2的那一對數  38           if (flag_sum  ==   1 ){     // sumA > sumB  39               for (i = 0 ; i  <  n; i ++ ) 40                   for (j = 0 ; j  <  n; j ++ ) 41                   42                       if (a[i]  >  b[j]){ 43                          num_diff  =  a[i]  -  b[j]; 44                           if (num_diff  <  sum_diff){ 45                              flag_num  = 1 ; 46                               if (num_diff  >=  temp1){ 47                                   if (num_diff - temp1  <  temp2){ 48                                      temp2  =  num_diff - temp1; 49                                      tempi  =  i; 50                                      tempj  =  j; 51                                  } 52                              } 53                               else { 54                                   if (temp1  -  num_diff  <  temp2){ 55                                      temp2  =  temp1  -  num_diff; 56                                      tempi  =  i; 57                                      tempj  =  j; 58                                  } 59                              } 60                          } 61                      } 62          } 63           else { 64               for (i = 0 ; i  <  n; i ++ ) 65                   for (j = 0 ; j  <  n; j ++ ) 66                   67                       if (a[i]  <  b[j]){ 68                          num_diff  =  b[j]  -  a[i]; 69                           if (num_diff  <  sum_diff){ 70                              flag_num  = 1 ; 71                               if (num_diff  >=  temp1){ 72                                   if (num_diff - temp1  <  temp2){ 73                                      temp2  =  num_diff - temp1; 74                                      tempi  =  i; 75                                      tempj  =  j; 76                                  } 77                              } 78                               else { 79                                   if (temp1  -  num_diff  <  temp2){ 80                                      temp2  =  temp1  -  num_diff; 81                                      tempi  =  i; 82                                      tempj  =  j; 83                                  } 84                              } 85                          } 86                      } 87          } 88   89           if (flag_num  ==   0 ) 90               break ; 91   92          temp  =  a[tempi]; 93          a[tempi]  =  b[tempj]; 94          b[tempj]  =  temp; 95       96          flag_num  =   0 ; 97          flag_sum  =   0 ; 98      } 99          100       for (i = 0 ; i  <  n;i ++ )101          PRintf( " %f/t " ,a[i]);102  103      printf( " /n " );104  105       for (i = 0 ; i  <  n;i ++ )106          printf( " %f/t " ,b[i]);107  108      printf( " /n " );    109      110       return   0 ;111  }112  113  114  int  main( int  argc,  char   * argv[])115  {116  117       float  a[ 3 ]  =  { 4 , 5 , 12 };118       float  b[ 3 ]  =  { 1 , 2 , 3 };119  120      test(a, b,  3 );121  122       return   0 ;123  }124