动态规划之什么是多重背包
本篇内容主要讲解“动态规划之什么是多重背包”，感兴趣的朋友不妨来看看。本文介绍的方法操作简单快捷，实用性强。下面就让小编来带大家学习“动态规划之什么是多重背包”吧!
站在用户的角度思考问题，与客户深入沟通，找到永昌网站设计与永昌网站推广的解决方案，凭借多年的经验，让设计与互联网技术结合，创造个性化、用户体验好的作品，建站类型包括：网站制作、做网站、企业官网、英文网站、手机端网站、网站推广、域名申请、网页空间、企业邮箱。业务覆盖永昌地区。
多重背包
有N种物品和一个容量为V 的背包。第i种物品最多有Mi件可用，每件耗费的空间是Ci ，价值是Wi 。求解将哪些物品装入背包可使这些物品的耗费的空间 总和不超过背包容量，且价值总和最大。
多重背包和01背包是非常像的， 为什么和01背包像呢?
每件物品最多有Mi件可用，把Mi件摊开，其实就是一个01背包问题了。
例如：
背包最大重量为10。
物品为：
| 重量 | 价值 | 数量 | |
|---|---|---|---|
| 物品0 | 1 | 15 | 2 |
| 物品1 | 3 | 20 | 3 |
| 物品2 | 4 | 30 | 2 |
问背包能背的物品最大价值是多少?
和如下情况有区别么?
| 重量 | 价值 | 数量 | |
|---|---|---|---|
| 物品0 | 1 | 15 | 1 |
| 物品0 | 1 | 15 | 1 |
| 物品1 | 3 | 20 | 1 |
| 物品1 | 3 | 20 | 1 |
| 物品1 | 3 | 20 | 1 |
| 物品2 | 4 | 30 | 1 |
| 物品2 | 4 | 30 | 1 |
毫无区别，这就转成了一个01背包问题了，且每个物品只用一次。
这种方式来实现多重背包的代码如下：
void test_multi_pack() { vector weight = {1, 3, 4}; vector value = {15, 20, 30}; vector nums = {2, 3, 2}; int bagWeight = 10; for (int i = 0; i < nums.size(); i++) { while (nums[i] > 1) { // nums[i]保留到1，把其他物品都展开 weight.push_back(weight[i]); value.push_back(value[i]); nums[i]--; } } vector dp(bagWeight + 1, 0); for(int i = 0; i < weight.size(); i++) { // 遍历物品 for(int j = bagWeight; j >= weight[i]; j--) { // 遍历背包容量 dp[j] = max(dp[j], dp[j - weight[i]] + value[i]); } for (int j = 0; j <= bagWeight; j++) { cout << dp[j] << " "; } cout << endl; } cout << dp[bagWeight] << endl; } int main() { test_multi_pack(); } 时间复杂度：O(m * n * k) m：物品种类个数，n背包容量，k单类物品数量
也有另一种实现方式，就是把每种商品遍历的个数放在01背包里面在遍历一遍。
代码如下：(详看注释)
void test_multi_pack() { vector weight = {1, 3, 4}; vector value = {15, 20, 30}; vector nums = {2, 3, 2}; int bagWeight = 10; vector dp(bagWeight + 1, 0); for(int i = 0; i < weight.size(); i++) { // 遍历物品 for(int j = bagWeight; j >= weight[i]; j--) { // 遍历背包容量 // 以上为01背包，然后加一个遍历个数 for (int k = 1; k <= nums[i] && (j - k * weight[i]) >= 0; k++) { // 遍历个数 dp[j] = max(dp[j], dp[j - k * weight[i]] + k * value[i]); } } // 打印一下dp数组 for (int j = 0; j <= bagWeight; j++) { cout << dp[j] << " "; } cout << endl; } cout << dp[bagWeight] << endl; } int main() { test_multi_pack(); } 时间复杂度：O(m * n * k) m：物品种类个数，n背包容量，k单类物品数量
从代码里可以看出是01背包里面在加一个for循环遍历一个每种商品的数量。和01背包还是如出一辙的。
当然还有那种二进制优化的方法，其实就是把每种物品的数量，打包成一个个独立的包。
到此，相信大家对“动态规划之什么是多重背包”有了更深的了解，不妨来实际操作一番吧！这里是创新互联网站，更多相关内容可以进入相关频道进行查询，关注我们，继续学习！
当前题目：动态规划之什么是多重背包
网站URL：http://6mz.cn/article/jdjoss.html