参与本项目，贡献其他语言版本的代码，拥抱开源，让更多学习算法的小伙伴们收益！
之前我们已经系统的讲解了01背包和完全背包，如果没有看过的录友，建议先把如下三篇文章仔细阅读一波。
这次我们再来说一说多重背包
对于多重背包，我在力扣上还没发现对应的题目，所以这里就做一下简单介绍，大家大概了解一下。
有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();
}
- 时间复杂度：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背包还是如出一辙的。
当然还有那种二进制优化的方法，其实就是把每种物品的数量，打包成一个个独立的包。
和以上在循环遍历上有所不同，因为是分拆为各个包最后可以组成一个完整背包，具体原理我就不做过多解释了，大家了解一下就行，面试的话基本不会考完这个深度了，感兴趣可以自己深入研究一波。
多重背包在面试中基本不会出现，力扣上也没有对应的题目，大家对多重背包的掌握程度知道它是一种01背包，并能在01背包的基础上写出对应代码就可以了。
至于背包九讲里面还有混合背包，二维费用背包，分组背包等等这些，大家感兴趣可以自己去学习学习，这里也不做介绍了，面试也不会考。
public void testMultiPack1(){
// 版本一：改变物品数量为01背包格式
List<Integer> weight = new ArrayList<>(Arrays.asList(1, 3, 4));
List<Integer> value = new ArrayList<>(Arrays.asList(15, 20, 30));
List<Integer> 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 <= nums[i] && (j - k * weight[i]) >= 0; k++) { // 遍历个数
dp[j] = Math.max(dp[j], dp[j - k * weight[i]] + k * value[i]);
}
System.out.println(Arrays.toString(dp));
}
}
}改变物品数量为01背包格式（无参版）
def test_multi_pack():
weight = [1, 3, 4]
value = [15, 20, 30]
nums = [2, 3, 2]
bagWeight = 10
# 将数量大于1的物品展开
for i in range(len(nums)):
while nums[i] > 1:
weight.append(weight[i])
value.append(value[i])
nums[i] -= 1
dp = [0] * (bagWeight + 1)
for i in range(len(weight)): # 遍历物品
for j in range(bagWeight, weight[i] - 1, -1): # 遍历背包容量
dp[j] = max(dp[j], dp[j - weight[i]] + value[i])
for j in range(bagWeight + 1):
print(dp[j], end=" ")
print()
print(dp[bagWeight])
test_multi_pack()改变遍历个数（无参版）
def test_multi_pack():
weight = [1, 3, 4]
value = [15, 20, 30]
nums = [2, 3, 2]
bagWeight = 10
dp = [0] * (bagWeight + 1)
for i in range(len(weight)): # 遍历物品
for j in range(bagWeight, weight[i] - 1, -1): # 遍历背包容量
# 以上为01背包，然后加一个遍历个数
for k in range(1, nums[i] + 1): # 遍历个数
if j - k * weight[i] >= 0:
dp[j] = max(dp[j], dp[j - k * weight[i]] + k * value[i])
# 打印一下dp数组
for j in range(bagWeight + 1):
print(dp[j], end=" ")
print()
print(dp[bagWeight])
test_multi_pack()改变物品数量为01背包格式（有参版）
def test_multi_pack(weight, value, nums, bagWeight):
# 将数量大于1的物品展开
for i in range(len(nums)):
while nums[i] > 1:
weight.append(weight[i])
value.append(value[i])
nums[i] -= 1
dp = [0] * (bagWeight + 1)
for i in range(len(weight)): # 遍历物品
for j in range(bagWeight, weight[i] - 1, -1): # 遍历背包容量
dp[j] = max(dp[j], dp[j - weight[i]] + value[i])
for j in range(bagWeight + 1):
print(dp[j], end=" ")
print()
print(dp[bagWeight])
if __name__ == "__main__":
weight = [1, 3, 4]
value = [15, 20, 30]
nums = [2, 3, 2]
bagWeight = 10
test_multi_pack(weight, value, nums, bagWeight)改变遍历个数（有参版）
def test_multi_pack(weight, value, nums, bagWeight):
dp = [0] * (bagWeight + 1)
for i in range(len(weight)): # 遍历物品
for j in range(bagWeight, weight[i] - 1, -1): # 遍历背包容量
# 以上为01背包，然后加一个遍历个数
for k in range(1, nums[i] + 1): # 遍历个数
if j - k * weight[i] >= 0:
dp[j] = max(dp[j], dp[j - k * weight[i]] + k * value[i])
# 使用 join 函数打印 dp 数组
print(' '.join(str(dp[j]) for j in range(bagWeight + 1)))
print(dp[bagWeight])
if __name__ == "__main__":
weight = [1, 3, 4]
value = [15, 20, 30]
nums = [2, 3, 2]
bagWeight = 10
test_multi_pack(weight, value, nums, bagWeight)package theory
import "log"
// 多重背包可以化解为 01 背包
func multiplePack(weight, value, nums []int, bagWeight int) int {
for i := 0; i < len(nums); i++ {
for nums[i] > 1 {
weight = append(weight, weight[i])
value = append(value, value[i])
nums[i]--
}
}
log.Println(weight)
log.Println(value)
res := make([]int, bagWeight+1)
for i := 0; i < len(weight); i++ {
for j := bagWeight; j >= weight[i]; j-- {
res[j] = getMax(res[j], res[j-weight[i]]+value[i])
}
log.Println(res)
}
return res[bagWeight]
}单元测试
package theory
import "testing"
func Test_multiplePack(t *testing.T) {
type args struct {
weight []int
value []int
nums []int
bagWeight int
}
tests := []struct {
name string
args args
want int
}{
{
name: "one",
args: args{
weight: []int{1, 3, 4},
value: []int{15, 20, 30},
nums: []int{2, 3, 2},
bagWeight: 10,
},
want: 90,
},
}
for _, tt := range tests {
t.Run(tt.name, func(t *testing.T) {
if got := multiplePack(tt.args.weight, tt.args.value, tt.args.nums, tt.args.bagWeight); got != tt.want {
t.Errorf("multiplePack() = %v, want %v", got, tt.want)
}
})
}
}输出
=== RUN Test_multiplePack
=== RUN Test_multiplePack/one
2022/03/02 21:09:05 [1 3 4 1 3 3 4]
2022/03/02 21:09:05 [15 20 30 15 20 20 30]
2022/03/02 21:09:05 [0 15 15 15 15 15 15 15 15 15 15]
2022/03/02 21:09:05 [0 15 15 20 35 35 35 35 35 35 35]
2022/03/02 21:09:05 [0 15 15 20 35 45 45 50 65 65 65]
2022/03/02 21:09:05 [0 15 30 30 35 50 60 60 65 80 80]
2022/03/02 21:09:05 [0 15 30 30 35 50 60 60 70 80 80]
2022/03/02 21:09:05 [0 15 30 30 35 50 60 60 70 80 80]
2022/03/02 21:09:05 [0 15 30 30 35 50 60 60 70 80 90]
--- PASS: Test_multiplePack (0.00s)
--- PASS: Test_multiplePack/one (0.00s)
PASS
版本一（改变数据源）：
function testMultiPack() {
const bagSize: number = 10;
const weightArr: number[] = [1, 3, 4],
valueArr: number[] = [15, 20, 30],
amountArr: number[] = [2, 3, 2];
for (let i = 0, length = amountArr.length; i < length; i++) {
while (amountArr[i] > 1) {
weightArr.push(weightArr[i]);
valueArr.push(valueArr[i]);
amountArr[i]--;
}
}
const goodsNum: number = weightArr.length;
const dp: number[] = new Array(bagSize + 1).fill(0);
// 遍历物品
for (let i = 0; i < goodsNum; i++) {
// 遍历背包容量
for (let j = bagSize; j >= weightArr[i]; j--) {
dp[j] = Math.max(dp[j], dp[j - weightArr[i]] + valueArr[i]);
}
}
console.log(dp);
}
testMultiPack();版本二（改变遍历方式）：
function testMultiPack() {
const bagSize: number = 10;
const weightArr: number[] = [1, 3, 4],
valueArr: number[] = [15, 20, 30],
amountArr: number[] = [2, 3, 2];
const goodsNum: number = weightArr.length;
const dp: number[] = new Array(bagSize + 1).fill(0);
// 遍历物品
for (let i = 0; i < goodsNum; i++) {
// 遍历物品个数
for (let j = 0; j < amountArr[i]; j++) {
// 遍历背包容量
for (let k = bagSize; k >= weightArr[i]; k--) {
dp[k] = Math.max(dp[k], dp[k - weightArr[i]] + valueArr[i]);
}
}
}
console.log(dp);
}
testMultiPack();
