#UVa:562-Dividing coins

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

C++(0.029)

/*******************************************************/
/* UVa 562 Dividing coins                              */
/* Author: LanyiKnight [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;
}
廣告

Comment

There is no comment on this post. Be the first one.

發表迴響

這個網站採用 Akismet 服務減少垃圾留言。進一步瞭解 Akismet 如何處理網站訪客的留言資料

%d 位部落客按了讚: