Skip to content

Latest commit

 

History

History
471 lines (366 loc) · 13.2 KB

背包问题理论基础多重背包.md

File metadata and controls

471 lines (366 loc) · 13.2 KB

参与本项目,贡献其他语言版本的代码,拥抱开源,让更多学习算法的小伙伴们收益!

动态规划:关于多重背包,你该了解这些!

之前我们已经系统的讲解了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背包的基础上写出对应代码就可以了。

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

其他语言版本

Java:

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));
        }
    }
}

Python:

改变物品数量为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)

Go:

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

TypeScript:

版本一(改变数据源):

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();