完全背包 分组背包巩固与强化
ACM-HDOJ 1171(多重背包水题)
Problem Description
Input
Output
Sample Input
Sample Output
题目要求
与1059题类似，只是输出变成了平分的结果，若不能平分则前者必须不小于后者。
参考AC代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57
| using namespace std; struct node { int value,num; }a[55]; int dp[250050]; int m; void ZeroOnePack(int value,int weight) { for(int v=m;v>=value;v--) dp[v]=max(dp[v],dp[v-value]+weight); } void CompletePack(int value,int weight) { for(int v=value;v<=m;v++) dp[v]=max(dp[v],dp[v-value]+weight); } void MultiPack(int value,int weight,int amount) { if(value*amount>=m) { CompletePack(value,weight); return; } for(int k=1;k<amount;k*=2) { ZeroOnePack(k*value,k*weight); amount-=k; } ZeroOnePack(amount*value,amount*weight); } int main() { int n; while(cin>>n && n>=0) { int sum=0; for(int i=1;i<=n;i++) { cin>>a[i].value>>a[i].num; sum+=a[i].value*a[i].num; } m=sum>>1; memset(dp,0,sizeof(dp)); for(int i=1;i<=n;i++) MultiPack(a[i].value,a[i].value,a[i].num); if(dp[m]==m) cout<<m<<" "<<m<<endl; else cout<<sum-dp[m]<<" "<<dp[m]<<endl; } return 0; }
|
思路
依旧运用背包模版进行解答，具体思路参考ACM-HDOJ 1059题。
多重背包模版的思路：若该物品价值大于背包最大容量则进入完全背包求解，否则进行01背包求解，其中可以进行二进制优化减少运算时间。(比如有价值为20的物品2个
，可以看成价值为20的物品和价值为20的物品，以此类推就转化为01背包问题了。)
转跳ACM-HDOJ 1059
注意事项
输出的前者必须大于等于后者，注意dp数组的大小是50×50×100.由于dp[m]是最优解，所以sum-dp[m]必然大于dp[m]。
其余参考ACM-HDOJ 1059题。
ACM-HDOJ 2191(多重背包水题)
Problem Description
Input
Output
Sample Input
Sample Output
参考AC代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51
| using namespace std; int dp[105],n; struct node { int v,w,num; }a[105]; void ZeroOnePack(int value,int weight) { for(int v=n;v>=value;v--) dp[v]=max(dp[v],dp[v-value]+weight); } void CompletePack(int value,int weight) { for(int v=value;v<=n;v++) dp[v]=max(dp[v],dp[v-value]+weight); } void MultiPack(int value,int weight,int amount) { if(value*amount>=n) { CompletePack(value,weight); return; } for(int k=1;k<amount;k*=2) { ZeroOnePack(k*value,k*weight); amount-=k; } ZeroOnePack(amount*value,amount*weight); } int main() { int t; cin>>t; while(t--) { int m; cin>>n>>m; for(int i=1;i<=m;i++) cin>>a[i].v>>a[i].w>>a[i].num; memset(dp,0,sizeof(dp)); for(int i=1;i<=m;i++) MultiPack(a[i].v,a[i].w,a[i].num); cout<<dp[n]<<endl; } return 0; }
|
思路
使用多重背包模版
注意事项
注意dp数组的大小。
ACM-HDOJ 1114(完全背包变形)
Problem Description
Input
Output
Sample Input
Sample Output
题目要求
完全背包变形。只是把求最优解变成了求装满背包的最小值。
参考AC代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37
| using namespace std; int dp[10005]; int sum; struct node { int p,w; }coin[550]; int main() { int t; cin>>t; while(t--) { int E,F,n; cin>>E>>F; sum=F-E; cin>>n; for(int i=0;i<n;i++) cin>>coin[i].p>>coin[i].w; for(int i=1;i<100005;i++) dp[i]=Inf; dp[0]=0; for(int i=0;i<n;i++) for(int j=coin[i].w;j<=sum;j++) dp[j]=min(dp[j],dp[j-coin[i].w]+coin[i].p); if(dp[sum]!=Inf) cout<<"The minimum amount of money in the piggy-bank is "<<dp[sum]<<"."<<endl; else cout<<"This is impossible."<<endl; } return 0; }
|
思路
与完全背包类似。dp的初始化为long int的最大值，dp[0]需初始化为0.另外把状态方程中的max换成min。最后判断dp[sum]的值是否为Inf，若等于则说明没有这样的最小
值。
注意事项
由于把最优解变成了求最小值，所以dp的初始化一定注意，要初始化为一个很大的数才行。
