Input示例
5 1 2 3 4 5
Output示例
1
分析:
2组的差最小,那么每一组都要接近sum/2,这样就转化成了普通的0 - 1背包了
#include <bits/stdc++.h> using namespace std; typedef long long LL; #define rep(i,a,n) for(int i = a; i < n; i++) #define repe(i,a,n) for(int i = a; i <= n; i++) #define per(i,n,a) for(int i = n; i >= a; i--) #define clc(a,b) memset(a,b,sizeof(a)) #define INF 0x3f3f3f3f3f #define N 1000010 const int MAXN = 110; int dp[10010]; int n,m; int val[MAXN]; int main() { while(cin >>n) { int sum = 0; for(int i = 1; i <= n; i++){ cin >>val[i]; sum += val[i]; } sort(val+1,val+n+1); memset(dp,0,sizeof(dp)); for(int i = 1; i <= n; i++){ for(int j = sum/2; j >= val[i]; j--){ dp[j] = max(dp[j],dp[j - val[i]]+val[i]); } } cout<<abs(sum - dp[sum/2]*2)<<endl; } }