多重背包问题简介🐳
有N种物品和一个容量为V 的背包。 第i种物品最多有Mi件可用，每件耗费的空间是Ci ，价值是Wi 。求解将哪些物品装入背包可使这些物品的耗费的空间总和不超过背包容量，且价值总和最大。
问题特征❓
不再像是01背包那样选或不选，而是 每个选项可以 选多次或者 不选。
转换思路😆
我们可以把完全背包问题转化为01背包问题，即将Mi件物品展开，如下：
完全背包表格：
展开，转化为01背包表格：
代码实现⭐
public void testMultiPack1(){
// 版本一：改变物品数量为01背包格式
List weight = new ArrayList<>(Arrays.asList(1, 3, 4));
List value = new ArrayList<>(Arrays.asList(15, 20, 30));
List nums = new ArrayList<>(Arrays.asList(2, 3, 2));
int bagWeight = 10;
for (int i = 0; i < nums.size(); i++) {
while (nums.get(i) > 1) { // 把物品展开为i
weight.add(weight.get(i));
value.add(value.get(i));
nums.set(i, nums.get(i) - 1);
}
}
int[] dp = new int[bagWeight + 1];
for(int i = 0; i < weight.size(); i++) { // 遍历物品
for(int j = bagWeight; j >= weight.get(i); j--) { // 遍历背包容量
dp[j] = Math.max(dp[j], dp[j - weight.get(i)] + value.get(i));
}
System.out.println(Arrays.toString(dp));
}
}
public void testMultiPack2(){
// 版本二：改变遍历个数
int[] weight = new int[] {1, 3, 4};
int[] value = new int[] {15, 20, 30};
int[] nums = new int[] {2, 3, 2};
int bagWeight = 10;
int[] dp = new int[bagWeight + 1];
for(int i = 0; i < weight.length; i++) { // 遍历物品
for(int j = bagWeight; j >= weight[i]; j--) { // 遍历背包容量
// 以上为01背包，然后加一个遍历个数
for (int k = 1; k = 0; k++) { // 遍历个数
dp[j] = Math.max(dp[j], dp[j - k * weight[i]] + k * value[i]);
}
System.out.println(Arrays.toString(dp));
}
}
}
//代码来自carl
Original: https://www.cnblogs.com/MyJyang/p/15967416.html
Author: Jyang~
Title: 多重背包问题
原创文章受到原创版权保护。转载请注明出处：https://www.johngo689.com/584652/
转载文章受原作者版权保护。转载请注明原作者出处！