首页 > 代码库 > hdu 1171 Big Event in HDU（背包DP）
hdu 1171 Big Event in HDU（背包DP）
题意：
杭电搬迁，有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;}
hdu 1171 Big Event in HDU（背包DP）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。