动态规划之什么是多重背包

本篇内容主要讲解“动态规划之什么是多重背包”，感兴趣的朋友不妨来看看。本文介绍的方法操作简单快捷，实用性强。下面就让小编来带大家学习“动态规划之什么是多重背包”吧!

多重背包

有N种物品和一个容量为V 的背包。第i种物品最多有Mi件可用，每件耗费的空间是Ci ，价值是Wi 。求解将哪些物品装入背包可使这些物品的耗费的空间  总和不超过背包容量，且价值总和最大。

多重背包和01背包是非常像的， 为什么和01背包像呢?

每件物品最多有Mi件可用，把Mi件摊开，其实就是一个01背包问题了。

例如：

背包最大重量为10。

物品为：

问背包能背的物品最大价值是多少?

和如下情况有区别么?

毫无区别，这就转成了一个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背包还是如出一辙的。

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

到此，相信大家对“动态规划之什么是多重背包”有了更深的了解，不妨来实际操作一番吧！这里是编程网网站，更多相关内容可以进入相关频道进行查询，关注我们，继续学习！