#UVa：562－Dividing coins

利用Dynamic Programming去做，題目其實就是要求利用這些硬幣能夠塞到的最接近總和平均的數值。

C++(0.029)

/*******************************************************/
/* UVa 562 Dividing coins                              */
/* Author: Maplewing [at] knightzone.studio            */
/* Version: 2015/05/07                                 */
/*******************************************************/
#include <iostream>
#include <cstdio>
#include <vector>
using namespace std;

int main(){
  int n;
  while( scanf("%d", &n) != EOF ){
    for( int testcase = 0 ; testcase < n ; ++testcase ){
      int m;
      scanf("%d", &m);

      int sum = 0;
      int coins[105] = {0};
      for( int i = 1 ; i <= m ; ++i ){
        scanf("%d", &coins[i]);
        sum += coins[i];
      }

      int average = sum / 2;
      vector<int> dp( average+5, 0 );
      for( int i = 1 ; i <= m ; ++i ){
        for( int j = average ; j >= coins[i] ; --j ){
          dp[j] = max( dp[j], dp[j-coins[i]] + coins[i] );
        }
      }

      printf("%d\n", (sum-dp[average]) - dp[average]);
    }
  }
  return 0;
}