题意:
杭电搬迁,有N种设备,每种设备有个价值V,数量M,要求将这些设备平分,使得平分后两边的总价值尽可能地相等。
输出两边各自的总价值。
思路:
背包DP后,P=所有的总价值/2,然后从P开始往两边找到第一个满足的价值。
可以降维,但是要注意for循环的顺序。
看代码。
代码:
int v[55], m[55]; bool dp[250005]; int main(){ int n; while(scanf("%d",&n)!=EOF && n>=0){ int tot = 0; rep(i,1,n){ scanf("%d%d",&v[i],&m[i]); tot += (v[i]*m[i]); } mem(dp,false); dp[0]=true; rep(i,1,n){ rep(j,1,m[i]){ rep2(k,tot,j*v[i]){ dp[k]=(dp[k] || dp[k-j*v[i]]); } } } int ts = tot/2; int ans1=-1,ans2=-1; rep2(i,ts,0){ if(dp[i] && dp[tot-i]){ ans1=i; ans2=tot-i; break; } } cout<<ans2<<" "<<ans1<<endl; } return 0; }