LeetCodeCampsDay37动态规划part05

完全背包问题

完全背包

01背包：每个物品最多只能被拿一次

完全背包：每个物品可被拿无限次数

举例，背包最大重量为4，物品为：

重量 价值
物品0 1 15
物品1 3 20
物品2 4 30

每件商品都有无限个！

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

  1. 确定dp数组与下标含义

先使用较好理解的二维dp数组：dp[i][j]表示从下标为从0到i的物品，每个物品可以取无限次，放进容量为j的背包，价值总和最大是多少

  1. 确定递推公式

以dp[1][4]为例，有两种情况，1）放物品1；2）不放物品1

如果装不下物品1，那背包的价值是dp[0][4]吗？即 只放物品0 并且容量为4的情况？如下图所示

img

img

没错，在装不下放物品1时的情况与01背包一致；

如果装得下物品1，那背包的价值上是max(dp[0][4], dp[0][4 - weight[1]] + val[4]) 吗？

并不是！在“装得下物品1时”的情况与01背包不同 （如下图所示）

在01背包时，因为物品1只能被装一次，所以我们只会考虑dp[0][4 - weight[1]] + val[4]的结果，而完全背包里，4 - weight[1] 是空出物品1的空间重量，但此时背包里也可能还有物品1 ，所以我们需要考虑dp[1][4 - weight[1]]而不是dp[0][4 - weight[1]]

即：

max(dp[0][4],dp[1][4−weight[1]+val[4])max(dp[0][4], dp[1][4 - weight[1] + val[4])

img

img

以上过程，抽象化如下：

  • 放不下物品i：背包容量为j，里面不放物品i的最大价值是dp[i - 1][j]。
  • 放得下物品i：背包誊出物品i的容量后，背包容量为j - weight[i]，dp[i][j - weight[i]] 为背包容量为j - weight[i]且不放物品i的最大价值，那么dp[i][j - weight[i]] + value[i] （物品i的价值），就是背包放物品i得到的最大价值

完全背包递推公式： dp[i][j] = max(dp[i - 1][j], dp[i][j - weight[i]] + value[i]);

01背包中递推公式： dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);

  1. 完全背包的dp数组初始化
    1. dp是个二维数组，大小为(n, capacity+1), dp = [[0] * (capacity + 1) for _ in range(n)]
    2. （第一列）先考虑容量为0的情况，dp[i][0] 全部设置为0
    3. （第一行）再考虑物品0的情况，如果背包能放得下物品0， 就一直放：dp[0][j] = dp[0][j - weight[0]] + val[0]
    4. 其它情况，因为其它值都会被覆盖，所以初始化为任意值都可以，初始化为0更方便罢了

img

  1. 遍历顺序

对于二维dp背包，可以先遍历物品再容量，也可以先容量再物品

1
2
3
4
5
6
7
8
# 注意从物品1开始，因为物品0已经初始化过了，不要重复遍历物品0
for i in range(1, n):
  for j in range(capacity):
    # 装不下物品i
    if j< weight[i]:
      dp[i][j] = dp[i - 1][j]
    else:
    	dp[i][j] = max(dp[i - 1][j], dp[i][j - weight[i]] + val[i])

携带研究材料（第七期模拟笔试）

https://kamacoder.com/problempage.php?pid=1052

题目描述

小明是一位科学家，他需要参加一场重要的国际科学大会，以展示自己的最新研究成果。他需要带一些研究材料，但是他的行李箱空间有限。这些研究材料包括实验设备、文献资料和实验样本等等，它们各自占据不同的重量，并且具有不同的价值。

小明的行李箱所能承担的总重量是有限的，问小明应该如何抉择，才能携带最大价值的研究材料，每种研究材料可以选择无数次，并且可以重复选择。

输入描述

第一行包含两个整数，n，v，分别表示研究材料的种类和行李所能承担的总重量

接下来包含 n 行，每行两个整数 wi 和 vi，代表第 i 种研究材料的重量和价值

输出描述

输出一个整数，表示最大价值。

输入示例

1
2
3
4
5
4 5
1 2
2 4
3 4
4 5

输出示例

1
10

提示信息

第一种材料选择五次，可以达到最大值。

数据范围：

1 <= n <= 10000;
1 <= v <= 10000;
1 <= wi, vi <= 10^9.

动态规划思路

二维完全背包动态规划代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
class solution():
    def foo(self, n: int, capacity: int, weight: list, val: list):
        # 创建dp（二维）
        dp = [[0] * (capacity + 1) for _ in range(n)]

        # 递推公式
        # dp[i][j] = max(dp[i - 1][j], dp[i][j - weight[i]] + val[i])

        # dp初始化，对物品一，只要能装下，就一直重复装物品一
        for i in range(weight[0], capacity + 1):
            dp[0][i] = dp[0][i - weight[0]] + val[0]
        
        # 遍历
        for i in range(1, n):
            for j in range(capacity + 1):
                if j < weight[i]:
                    dp[i][j] = dp[i - 1][j]
                else:
                    dp[i][j] = max(dp[i - 1][j], dp[i][j - weight[i]] + val[i])
        
        # 输出dp[-1][-1]
        # print(dp)
        print(dp[n - 1][capacity])

n, capacity = map(int, input().split(" "))
weight = list()
val = list()
for i in range(n):
    w, v = map(int, input().split())
    weight.append(w)
    val.append(v)
s = solution()

s.foo(n, capacity, weight, val)

一维完全背包思路

简直来说就是将二维完全背包压缩，但！在遍历时，对容量的遍历不用从大到小遍历，而必须从小到大遍历

在遍历容量时

  1. （一维dp）01背包必须从大到小遍历
  2. （一维、二维dp）完全背包必须从小到大遍历

我在完全背包（一维DP）中讲解了完全背包的两个for循环的先后顺序都是可以的。

但本题就不行了！

因为纯完全背包求得装满背包的最大价值是多少，和凑成总和的元素有没有顺序没关系，即：有顺序也行，没有顺序也行！

而本题要求凑成总和的组合数 ，元素之间明确要求没有顺序 。

所以纯完全背包是能凑成总和就行，不用管怎么凑的。

本题是求凑出来的方案个数，且每个方案个数是组合数。

那么本题，两个for循环的先后顺序可就有说法了。

我们先来看 外层for循环遍历物品（钱币），内层for遍历背包（金钱总额）的情况。

代码如下：

1
2
3
4
5
for (int i = 0; i < coins.size(); i++) { // 遍历物品
    for (int j = coins[i]; j <= amount; j++) { // 遍历背包容量
        dp[j] += dp[j - coins[i]];
    }
}

假设：coins[0] = 1，coins[1] = 5。

那么就是先把1加入计算，然后再把5加入计算，得到的方法数量只有{1, 5}这种情况。而不会出现{5, 1}的情况。

所以这种遍历顺序中dp[j]里计算的是组合数！

如果把两个for交换顺序，代码如下：

1
2
3
4
5
for (int j = 0; j <= amount; j++) { // 遍历背包容量
    for (int i = 0; i < coins.size(); i++) { // 遍历物品
        if (j - coins[i] >= 0) dp[j] += dp[j - coins[i]];
    }
}

背包容量的每一个值，都是经过 1 和 5 的计算，包含了{1, 5} 和 {5, 1}两种情况。

此时dp[j]里算出来的就是排列数！

可能这里很多同学还不是很理解，建议动手把这两种方案的dp数组数值变化打印出来，对比看一看！（实践出真知）

一维完全背包动态规划代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
def bar(self, n: int, capacity: int, weight: list, val: list):
        # 创建dp（一维）
        dp = [0] * (capacity + 1)

        # 递推公式
        # dp[j] = max([j], dp[j - weight[i]] + val[i])

        # dp初始化，对物品一，只要能装下，就一直重复装物品一
        for i in range(weight[0], capacity + 1):
            dp[i] = dp[i - weight[0]] + val[0]
        
        # 遍历
        for i in range(1, n):
            for j in range(capacity + 1):
                if j >= weight[i]:
                    dp[j] = max(dp[j], dp[j - weight[i]] + val[i])
        
        print(dp[- 1])

518. 零钱兑换 II

https://leetcode.cn/problems/coin-change-ii/

给你一个整数数组 coins 表示不同面额的硬币，另给一个整数 amount 表示总金额。

请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额，返回 0 。

假设每一种面额的硬币有无限个。

题目数据保证结果符合 32 位带符号整数。

示例 1：

1
2
3
4
5
6
7
输入：amount = 5, coins = [1, 2, 5]
输出：4
解释：有四种方式可以凑成总金额：
5=5
5=2+2+1
5=2+1+1+1
5=1+1+1+1+1

示例 2：

1
2
3
输入：amount = 3, coins = [2]
输出：0
解释：只用面额 2 的硬币不能凑成总金额 3 。

示例 3：

1
2
输入：amount = 10, coins = [10] 
输出：1

提示：

  • 1 <= coins.length <= 300
  • 1 <= coins[i] <= 5000
  • coins 中的所有值 互不相同
  • 0 <= amount <= 5000

动态规划思路

本题求的是装满这个背包的物品组合数是多少

注意，组合数不要求顺序：比如(1,5)和(5,1)是同一组合

而，排列要求顺序，(1,5)与(5,1)不是同一排列

例如示例一：

5 = 2 + 2 + 1

5 = 2 + 1 + 2

这是一种组合，都是 2 2 1。

如果问的是排列数，那么上面就是两种排列了。

组合不强调元素之间的顺序，排列强调元素之间的顺序。 为什么要介绍这些呢，因为这和下文讲解遍历顺序 息息相关!

本题目和494.目标和几乎一样，都是求组合数，本题是完全背包而494.是01背包

  1. 定义二维dp数值 dp[i][j]：使用 下标为[0, i]的coins[i]能够凑满j（包括j）这么大容量的包，有dp[i][j]种组合方法。

  2. 递推关系

如果coins[i] <= j则

在，01背包理论基础 ，中二维DP数组的递推公式为：

1
dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i])

在 完全背包理论基础详细讲解了完全背包二维DP数组的递推公式为：

1
dp[i][j] = max(dp[i - 1][j], dp[i][j - weight[i]] + value[i])

如果coins[i] > j则

dp[i][j] = dp[i - 1][j]

在494. 目标和中详解讲解了装满背包有几种方法，二维DP数组的递推公式： dp[i][j] = dp[i - 1][j] + dp[i - 1][j - nums[i]]

所以完全背包里的装满背包有几种方法，二维DP数组的递推公式：dp[i][j] = dp[i - 1][j] + dp[i][j - nums[i]]

区别依然是 dp[i - 1][j - nums[i]] 和 dp[i][j - nums[i]]

稍微解释下吧，dp[i - 1][j]是不带物品i，容量j时的组合方法数，而dp[i][j - nums[i]]是带物品i，容量j的组合方法数，相加才是物品i，容量j的组合方法数

  1. 初始化

我的想法：

将dp[i][0]初始化为1，意义？amount=0，只有一种方式；反过来想，如果令dp[i][0]等于0，后面需要加上dp[i][5 - 5] = 0这种情况时就没有意义了；其它数全初始化为0

但这样就必须在遍历时从物品0开始

for i in range(len(coins)):

卡哥想法：

img

img

把dp的第一行、第一列进行初始化，dp[0][0]初始化为0；

第一行dp[0][j]，它的含义是用 [物品0] 装满 背包容量为j 的背包，有多少组合；

如果j可以整除物品0，那么它则有一种组合方法

1
2
3
for (int j = 0; j <= amount; j++) {
    if (j % coins[0] == 0) dp[0][j] = 1;
}

这样的初始化，在遍历时就必须从物品1开始

for i in range(1, len(coins)):

第一列dp[i][0]，用物品i 装满容量为0的背包，只有一种方法：不装

1
2
for i in range(Lc):
    dp[i][0] = 1
  1. 遍历顺序

二维数组dp遍历顺序先容量/先物品都可以

二维动态规划代码

  • 时间复杂度O(mn)
  • 空间复杂度O(mn)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution:
    def change(self, amount: int, coins: List[int]) -> int:
        # 问题转换：完全背包，装成target值，有多少种组合方式？
        # dp[i][j] 表示物品i（金币i）组成金额j的组合方式数。

        
        # ---正式代码---
        Lc = len(coins)
        dp = [[0] * (amount + 1) for _ in range(Lc)]
        # 初始化
        for i in range(Lc):
            dp[i][0] = 1

        for i in range(Lc):
            # 从
            for j in range(amount + 1):
                if j >= coins[i]:
                    dp[i][j] = dp[i - 1][j] + dp[i][j - coins[i]]
                else:
                    dp[i][j] = dp[i - 1][j]

        return dp[-1][-1]

377. 组合总和 Ⅳ

https://leetcode.cn/problems/combination-sum-iv/

给你一个由 不同 整数组成的数组 nums ，和一个目标整数 target 。请你从 nums 中找出并返回总和为 target 的元素组合的个数。

题目数据保证答案符合 32 位整数范围。

示例 1：

1
2
3
4
5
6
7
8
9
10
11
12
输入：nums = [1,2,3], target = 4
输出：7
解释：
所有可能的组合为：
(1, 1, 1, 1)
(1, 1, 2)
(1, 2, 1)
(1, 3)
(2, 1, 1)
(2, 2)
(3, 1)
请注意，顺序不同的序列被视作不同的组合。

示例 2：

1
2
输入：nums = [9], target = 3
输出：0

提示：

  • 1 <= nums.length <= 200
  • 1 <= nums[i] <= 1000
  • nums 中的所有元素 互不相同
  • 1 <= target <= 1000

**进阶：**如果给定的数组中含有负数会发生什么？问题会产生何种变化？如果允许负数出现，需要向题目中添加哪些限制条件？

二维动态规划代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution:
    def combinationSum4(self, nums: List[int], target: int) -> int:
        # 完全背包，装满为target的值，问方式数量
        # 这题目与518不同点在于，本题的不同顺序可以看成不同求排列
        # 比如1，1，2与1，2，1就是两种求排列

        # dp二维，dp[i][j]，表示在物品i价值为j的情况下求排列数
        
        # 递推公式：dp[i][j] = dp[i - 1][j] + dp[i][j - nums[i]] + dp[j - nums[i]][i]

        # dp初始化，首先，dp维度是(target + 1, len(nums) + 1)
        # 
        L = len(nums)
        dp = [[0] * (target + 1) for _ in range(L)]
        # 且dp[i][0]全为1，除了dp[0][0]必须为0，所以跳过第一行
        for i in range(L):
            dp[i][0] = 1
        print(dp)
        # 遍历顺序，先物品，再容量
        # 这可以跳过第一个
        for j in range(1, target + 1):
            for i in range(L):
                print(dp)
                if j >= nums[i]:
                    dp[i][j] = dp[i - 1][j] + dp[-1][j - nums[i]]
                else:
                    dp[i][j] = dp[i - 1][j]
        
        return dp[-1][-1]

一维动态规划代码

1
2
3
4
5
6
7
8
9
10
L = len(nums)
dp = [0] * (target + 1)
dp[0] = 1
# 
for i in range(1, target + 1):
    for j in range(L):
        if i >= nums[j]:
            dp[i] += dp[i - nums[j]]
return dp[-1]