**joj 1903 tug of war 使用动态规划

?1903: Tug of War

---

ResultTIME LimitMEMORY LimitRun TimesAC TimesJUDGE15s8192K556123Standard/*使用动态规划计算tug of war 其实动态规划类似于搜索搜索所有可能的状态，分辨哪些是可达的*/#include<iostream> using namespace std; int n,w[103],sum,ans,l,r; bool dp[45005][103]; //row:表示重量 col:表示人数int main() { int i; // freopen("in.txt","r",stdin); //freopen("car.out","w",stdout); while(scanf("%d", &n) != EOF){memset(dp, 0, sizeof(dp)); sum=0; for(i=1;i<=n;i++)scanf("%d",&w[i]),sum+=w[i]; dp[0][0]=1; //表明体重是0 人数是0这个状态是可达的dp[0][101]=1;//人数最多是100，所以此时也是可达的/*下面两重循环首先计算出dp[w[i]][101] = 1,然后在向上累加*/for(i=1;i<=n;++i) //人数开始循环for(int j=sum;j>=w[i];--j) //体重开始循环，倒着推，可以避免重复计算？？？if(dp[j-w[i]][101]) { dp[j][101]=1; //如果dp[j-w[i]][101]可达，那么增加体重后dp[j][101]=1一定可达/*如果dp[0][0]可达，那么dp[w[i]][1]可达，所以如果dp[j-w[i]][k]可达，那么增加体重（同时也要增加人数）的dp[j][k+1]=1; 一定可达*/for(int k=0;k<n;k++) if(dp[j-w[i]][k])dp[j][k+1]=1; } ans=sum/2; //最理想的状况是sum的一半 while(!(dp[ans][101] && (dp[ans][n/2] || dp[ans][(n+1)/2]))) //如果此时状态不可达，那么ans减小--ans; printf("%d %d\n",ans,sum-ans); }return 0; }

这种方法有局限性，只能适用于给数数据的上限，比如最多100人，每个人的体重最大450.如果没有这种限制，则不能使用dp。可以使用随机方法