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;
}