本文主要是介绍Big Event in HDU HDU - 1171 （多重背包），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
Big Event in HDU
题目链接：HDU - 1171
题意：hdu的计算机学院要分成两个院系，原学院有多个设备，知道每种设备的价值和已有的数量，问分配已有的设备，是最公平的，求出分配后每个院分到的设备价值；
很明显的一个多重背包，由于数据小，可以转换成01背包；
多重背包代码：
#include <bits/stdc++.h>
using namespace std;
int dp[250010];
int v[100], m[100];
int main(){int n;while(scanf("%d", &n), n>=0){memset(dp, 0, sizeof(dp));int sum=0;for(int i=1; i<=n; i++){scanf("%d%d", &v[i], &m[i]);sum+=v[i]*m[i];}int temp=sum;sum/=2;for(int i=1; i<=n; i++){if(v[i]*m[i]>=sum){for(int j=v[i]; j<=sum; j++){dp[j]=max(dp[j], dp[j-v[i]]+v[i]);}}else{int k=1;while(k<=m[i]){for(int j=sum; j>=k*v[i]; j--){dp[j]=max(dp[j], dp[j-k*v[i]]+k*v[i]);}m[i]-=k;k<<=1;}for(int j=sum; j>=m[i]*v[i]; j--){dp[j]=max(dp[j], dp[j-m[i]*v[i]]+m[i]*v[i]);}}}int A, B;A=max(dp[sum], temp-dp[sum]);B=temp-A;printf("%d %d\n", A, B);}return 0;
}
01背包代码
#include <bits/stdc++.h>
using namespace std;
int dp[250010];
int v[5100];
int main(){int N;while(scanf("%d", &N), N>=0){memset(dp, 0, sizeof(dp));int cnt=0;int sum=0;for(int i=0; i<N; i++){int V, M;scanf("%d%d", &V, &M);sum+=V*M;for(int j=0; j<M; j++)v[++cnt]=V;}int temp=sum;sum/=2;for(int i=1; i<=cnt; i++){for(int j=sum; j>=v[i]; j--){dp[j]=max(dp[j], dp[j-v[i]]+v[i]);}}int A=max(dp[sum], temp-dp[sum]);printf("%d %d\n", A, temp-A);}return 0;
}
这篇关于Big Event in HDU HDU - 1171 （多重背包）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
