UVa-562, LiveArchive-5583 : Dividing coins
問題概要
N(<100)枚のコインがある。コインの価値はそれぞれC[i](<500)である。これらを二つの集合に分けて部分和の差を最小化する問題。
解法
部分和問題のNが大きい番。半分全列挙は使えないが、値が小さいのでDPで作ることのできる部分和を全て求める。
acceptされたコード
計算量O(N^2*C)。
#include <cstdio> #include <algorithm> #include <cstring> #include <numeric> using namespace std; const int MAX_N = 100; const int MAX_V = 500; int N; bool dp[MAX_N*MAX_V + 1]; int as[MAX_N]; void init(){ scanf("%d", &N); for(int i=0; i<N; i++){ scanf("%d", as+i); } memset(dp, false, sizeof(dp)); } int solve(){ int sum = accumulate(as, as+N, 0); dp[0] = true; for(int i=0; i<N; i++){ for(int j=MAX_V*MAX_N; j>=0; j--)if(dp[j]){ dp[j+as[i]] = true; } } int ans = MAX_N * MAX_V; for(int i=0; i<=MAX_V*MAX_N; i++){ if(dp[i]){ ans = min(ans, abs(sum-2*i)); } } return ans; } int main(){ int T; scanf("%d", &T); while(T--){ init(); printf("%d\n", solve()); } return 0; }