题意：给定n个硬币，要求将这些硬币平分以使两个人获得的钱尽量多，求两个人分到的钱最小差值。 思路：先将所有硬币的总额算出来为sum，以sum/2为背包容量，算出dp[sum/2]，然后abs(sum-2*dp[sum/2])就是最小的差值；
#include<iostream> #include<algorithm> #include<string> #include<cstring> #include<map> #include<queue> #include<cmath> #include<stack> #include<vector> #include<cstdio> #define MAXN 33000 #define INF 0x3f3f3f3f #define lmid l,m,rt<<1 #define rmid m+1,r,rt<<1|1 #define ls rt<<1 #define rs rt<<1|1 #define Mod 1000000007 #define i64 __int64 using namespace std; int num[105]; int dp[30000]; int main() { int t; scanf("%d",&t); while(t--) { memset(dp,0,sizeof(dp)); int sum=0; int n; scanf("%d",&n); for(int i=0;i<n;i++) { scanf("%d",&num[i]); sum+=num[i]; } int m=(sum+1)/2; for(int i=0;i<n;i++) for(int j=m;j>=num[i];j--) { dp[j]=max(dp[j],dp[j-num[i]]+num[i]); } cout<<abs(sum-2*dp[m])<<endl; } return 0; }