刚开始一直在纠结怎么记录人数，因为一开始的想法是dp[i][j]表示前i个人是否能达j这个值，想过用状态压缩存储路径，然后发现状态压缩只适合在人数<20时，时间和空间复杂度才可以接受，也想过用数组存储人数，但也不好操作，看了别人的解题报告，才发现自己想太多了，这里根本不需要知道路径，只需要知道到达j这个值时，有多少个人就可以了，
POJ 2576 Tug of War
。所以直接加一个状态表示人数，于是状态就变成了：dp[i][k][j]表示前i 个人时，选k个人时，是否能到达j值然后考虑到空间复杂度，省略i这个状态，用逆序保证每个人只选一次
#include<stdio.h>#include<string.h>int dp[105][45005],w[105];int n;void init(){ memset(dp,0,sizeof(dp)); dp[0][0]=1;}int main(){ #ifndef ONLINE_JUDGE freopen("in.txt","r",stdin); #endif scanf("%d",&n); int sum=0; for(int i=1;i<=n;i++) { scanf("%d",&w[i]); sum+=w[i]; } init(); for(int i=1;i<=n;i++){ for(int j=sum;j-w[i]>=0;j--){ for(int k=n/2+1;k>=1;k--){ if(dp[k-1][j-w[i]]) { dp[k][j]=dp[k-1][j-w[i]]; } } } } for(int i=sum/2;i>=0;i--){ if(n&1) { if(dp[n/2][i]||dp[n/2+1][i]) { printf("%d %d\n",i,sum-i); break; } } else{ if(dp[n/2][i]) { printf("%d %d\n",i,sum-i); break; } } } return 0;}</string.h></stdio.h>