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

多重背包

创新互联建站是一家专注于成都网站设计、网站建设与策划设计,永昌网站建设哪家好?创新互联建站做网站,专注于网站建设十多年,网设计领域的专业建站公司;建站业务涵盖:永昌等地区。永昌做网站价格咨询:028-86922220

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

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

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

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

例如：

背包最大重量为10。

物品为：

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

和如下情况有区别么?

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

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

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

总结

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

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

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

当前名称：动态规划：关于多重背包，你该了解这些！
URL链接：http://www.shufengxianlan.com/qtweb/news8/178708.html

网站建设、网络推广公司-创新互联，是专注品牌与效果的网站制作，网络营销seo公司；服务项目有等

广告

声明：本网站发布的内容（图片、视频和文字）以用户投稿、用户转载内容为主，如果涉及侵权请尽快告知，我们将会在第一时间删除。文章观点不代表本网站立场，如需处理请联系客服。电话：028-86922220；邮箱：631063699@qq.com。内容未经允许不得转载，或转载时需注明来源： 创新互联