动态规划：关于多重背包，你该了解这些！

多重背包

对于多重背包，动态多重我在力扣上还没发现对应的规划关于该解题目，所以这里就做一下简单介绍，背包大家大概了解一下。动态多重

有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<int> weight = { 1, 3, 4};     vector<int> value = { 15, 20, 30};     vector<int> 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<int> 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<int> weight = { 1, 3, 4};     vector<int> value = { 15, 20, 30};     vector<int> nums = { 2, 3, 2};     int bagWeight = 10;     vector<int> 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背包还是如出一辙的。

当然还有那种二进制优化的方法，其实就是把每种物品的数量，打包成一个个独立的云南idc服务商包。

和以上在循环遍历上有所不同，因为是分拆为各个包最后可以组成一个完整背包，具体原理我就不做过多解释了，大家了解一下就行，面试的话基本不会考完这个深度了，感兴趣可以自己深入研究一波。

总结

多重背包在面试中基本不会出现，力扣上也没有对应的题目，大家对多重背包的掌握程度知道它是一种01背包，并能在01背包的基础上写出对应代码就可以了。

至于背包九讲里面还有混合背包，二维费用背包，分组背包等等这些，大家感兴趣可以自己去学习学习，这里也不做介绍了，面试也不会考。

本文转载自微信公众号「代码随想录」，可以通过以下二维码关注。转载本文请联系代码随想录公众号。服务器托管