本文主要是介绍悼念512汶川大地震遇难同胞——珍惜现在，感恩生活 HDU - 2191 （多重背包），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
悼念512汶川大地震遇难同胞——珍惜现在，感恩生活
题目链接：HDU - 2191
题意：现共有资金n，采购大米，有m种大米，已知每种大米的价格(每袋)，重量(每袋)，以及库存；问最多能购得多少大米，大米只能按袋买；
思路：每种物品有xi个，是多重背包，可以直接套用多重背包计算，
再者，题目数据很小，可以直接把多重背包转换成01背包；
多重背包代码：
#include <bits/stdc++.h>
using namespace std;
int dp[110], p[110], h[110], c[110];
int main(){int C;scanf("%d", &C);while(C--){int n, m;scanf("%d%d", &n, &m);for(int i=1; i<=m; i++){scanf("%d%d%d", &p[i], &h[i], &c[i]);}memset(dp, 0, sizeof(dp));for(int i=1; i<=m; i++){if(n<=p[i]*c[i]){for(int j=p[i]; j<=n; j++){dp[j]=max(dp[j], dp[j-p[i]]+h[i]);}}else{int k=1;while(k<=c[i]){for(int j=n; j>=k*p[i]; j--){dp[j]=max(dp[j], dp[j-k*p[i]]+h[i]*k);}c[i]-=k;k<<=1;}for(int j=n; j>=p[i]*c[i]; j--){dp[j]=max(dp[j], dp[j-p[i]*c[i]]+h[i]*c[i]);}}}printf("%d\n", dp[n]);}return 0;
}
01背包代码：
#include <bits/stdc++.h>
using namespace std;
int dp[110], p[2100], h[2100];
int main(){int C;scanf("%d", &C);while(C--){int n, m;scanf("%d%d", &n, &m);memset(dp, 0, sizeof(dp));int cnt=0;for(int i=1; i<=m; i++){int pp, hh, cc;scanf("%d%d%d", &pp, &hh, &cc);for(int j=0; j<cc; j++){p[++cnt]=pp;h[cnt]=hh;}}for(int i=1; i<=cnt; i++){for(int j=n; j>=p[i]; j--){dp[j]=max(dp[j], dp[j-p[i]]+h[i]);}}printf("%d\n", dp[n]);}return 0;
}
这篇关于悼念512汶川大地震遇难同胞——珍惜现在，感恩生活 HDU - 2191 （多重背包）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
