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

Bertha 。 2023-10-16 17:10 21阅读 0赞

## 多重背包 ##

对于多重背包，力扣上还没发现对应的题目。

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

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

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

例如：  
背包最大重量为10。

物品为：

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

和如下情况有区别么？

毫无区别，这就转成了一个01背包问题了，且每个物品只用一次。

也有另一种实现方式，就是把每种商品遍历的个数放在01背包里面在遍历一遍。

## 总结 ##

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

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

**参考资料**：[代码随想录-动态规划：关于多重背包，你该了解这些！][-]

[-]: https://programmercarl.com/%E8%83%8C%E5%8C%85%E9%97%AE%E9%A2%98%E7%90%86%E8%AE%BA%E5%9F%BA%E7%A1%80%E5%A4%9A%E9%87%8D%E8%83%8C%E5%8C%85.html#%E5%A4%9A%E9%87%8D%E8%83%8C%E5%8C%85

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

发表评论取消回复

还没有评论，来说两句吧...

相关阅读

相关【动态规划】代码随想录算法训练营第四十六天 |139.单词拆分，关于多重背包，你该了解这些！，背包问题总结篇！（待补充）

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

相关关于贪心算法，你该了解这些！

相关背包问题详解（动态规划）：01背包、完全背包、多重背包

相关关于 Java 反射，你该了解这些

相关关于python函数，你该了解这些

相关【动态规划】完全背包、多重背包

相关 poj1742 动态规划经典多重背包

相关动态规划解二维多重背包问题

相关【动态规划】三种背包问题（01背包、完全背包、多重背包）