多重背包
对于多重背包,我在力扣上还没发现对应的题目,所以这里就做一下简单介绍,大家大概了解一下。
有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();
- }
也有另一种实现方式,就是把每种商品遍历的个数放在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();
- }
从代码里可以看出是01背包里面在加一个for循环遍历一个每种商品的数量。和01背包还是如出一辙的。
当然还有那种二进制优化的方法,其实就是把每种物品的数量,打包成一个个独立的包。
和以上在循环遍历上有所不同,因为是分拆为各个包最后可以组成一个完整背包,具体原理我就不做过多解释了,大家了解一下就行,面试的话基本不会考完这个深度了,感兴趣可以自己深入研究一波。
总结
多重背包在面试中基本不会出现,力扣上也没有对应的题目,大家对多重背包的掌握程度知道它是一种01背包,并能在01背包的基础上写出对应代码就可以了。
至于背包九讲里面还有混合背包,二维费用背包,分组背包等等这些,大家感兴趣可以自己去学习学习,这里也不做介绍了,面试也不会考。
本文转载自微信公众号「代码随想录」,可以通过以下二维码关注。转载本文请联系代码随想录公众号。
本文转载自微信公众号「架构精进之路」,作者架构精进之路。转载本文请联系架构...
尽管云计算技术已经推出十多年的时间,但企业从私有云、内部部署或公共云环境中...
TOP云 (west.cn)12月14日消息,最新一期的DN榜刚刚出炉,本期榜单上多个数字 ...
2020年12月9日在北京举办的“2020第三代人工智能产业论坛”上,中国信息通信研究...
这一课讨论关于容错(Fault-Tolerance)和复制(Replication)的问题,主要研究 VMwa...
百度智能云工业质检智能化解决文案 人工智能开启传统制造业新时代 TOP云(zuntop...
连接计算机内核和交互界面的桥梁叫做终端,在下面这样黑乎乎的窗口敲代码才有高...
云服务器 内存不够了怎么办? 云服务器 内存,是其配置参数之一。内存大小也是影...
作者 | 王骜 来源 | Serverless 公众号 导读 ? USENIX ATC (USENIX Annual Techn...
前言 最近加入到一个新的团队,整体的框架方向是构建业务中台,划分子域、上下文...