背包问题

背包问题包括以下几种情况：

图片来自carl哥的：代码随想录 侵删

---

0-1背包问题

​ 有n件物品和一个最多能背重量为w 的背包。第i件物品的重量是weight[i]，得到的价值是value[i] 。每件物品只能用一次，求解将哪些物品装入背包里物品价值总和最大。

解法一：二维DP数组

首先我们需要确定三要数：状态转移方程、初始状态和遍历顺序

举例：

首先我们确定状态转移方程：dp[i] [j] 表示装前i个物品里，放进容量为j的背包，价值总和最大是多少。

分析两种情况：

​ 一、那么我们可以在选择第i个物品时，发现它的重量大于我们背包重量（装不下）此时dp[i] [j] = dp[i-1] [j] (此时最大价值仍然是选择前几个物品的价值)

​ 二、选择第i个物品时，满足背包重量要求，此时我可以选择不放进去，或者选择放进去

• 如果不放进去，此时dp[i][j] = dp[i-1][j]

• 放进去，那么我们就相当于从背包腾出weight的空间来确定价值,

  dp[i][j] = dp[i-1][j-weight] + val

最终状态转移方程为 dp[i][j] = max(dp[i-1][j], dp[i][j] = dp[i-1][j-weight] + val )

然后确定初始状态：

for i in range(rows):	#选择任意物品放入背包重量为0的背包，那么价值为0
    dp[i][0] = 0
first_item_weight, first_item_value = weight[0], value[0]
for j in range(1, cols): # 选择第一个物品放入背包中，满足背包重量条件，那么价值为物品价值
    if first_item_weight <= j:
        dp[0][j] = first_item_value
        
1
2
3
4
5
6
7

遍历顺序？ 实际上无论是先遍历背包还是遍历物品都是一样的，因为我们的状态转移方程只与上一行有关，不影响公式的推导。这里我们以先遍历物品再遍历背包为例。

for i in range(1, len(weight)):
    cur_weight, cur_val = weight[i], value[i]
    for j in range(1, cols):
        if cur_weight > j:  # 说明背包装不下当前物品.
            dp[i][j] = dp[i - 1][j]  # 所以不装当前物品.
        else:
            # 定义dp数组: dp[i][j] 前i个物品里，放进容量为j的背包，价值总和最大是多少。
            dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - cur_weight] + cur_val)
1
2
3
4
5
6
7
8

解法二：一维DP数组

因为状态的转移只与上一层有关，所以我们可以用滚动数组优化空间。

确定转移方程：dp[j] = max(dp[j],dp[j-weight]+value dp[j]表示背包重量为j时所能容纳的最大价值

初始化条件： dp[0] = 0

遍历：

# 先遍历物品, 再遍历背包容量
for i in range(len(weight)):
    for j in range(bag_weight, weight[i] - 1, -1):  # 注意是倒序遍历，正序遍历会导致物品重复放入
        # 递归公式
        dp[j] = max(dp[j], dp[j - weight[i]] + value[i])
1
2
3
4
5

注：在这里遍历顺序不可以颠倒，首先我们的背包得保证倒序遍历，这样做是为了防止物品重复放入（完全背包）

其次，如果颠倒顺序，背包又需要倒序遍历的话，会导致我们最后只放入一个物品！

---

完全背包问题

​ 有N件物品和一个最多能背重量为W的背包。第i件物品的重量是weight[i]，得到的价值是value[i] 。每件物品都有无限个（也就是可以放入背包多次），求解将哪些物品装入背包里物品价值总和最大。

完全背包和01背包问题唯一不同的地方就是，每种物品有无限件。

完全背包中，先遍历物品还是先遍历背包都可以

因为dp[j] 是根据 下标j之前所对应的dp[j]计算出来的。 只要保证下标j之前的dp[j]都是经过计算的就可以了。

# 先遍历物品，再遍历背包
def test_complete_pack1():
    weight = [1, 3, 4]
    value = [15, 20, 30]
    bag_weight = 4

    dp = [0] * (bag_weight + 1)  # 背包体积为j时所装的最大价值

    for i in range(len(weight)):
        for j in range(weight[i], bag_weight + 1):
            dp[j] = max(dp[j], dp[j - weight[i]] + value[i])

    print(dp[bag_weight])


# 先遍历背包，再遍历物品
def test_complete_pack2():
    weight = [1, 3, 4]
    value = [15, 20, 30]
    bag_weight = 4

    dp = [0] * (bag_weight + 1)

    for j in range(bag_weight + 1):
        for i in range(len(weight)):
            if j >= weight[i]:      # 如果背包体积大于物品体积
                dp[j] = max(dp[j], dp[j - weight[i]] + value[i])

    print(dp[bag_weight])
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

---

组合和排列问题

组合不强调顺序、排列强调顺序！

这样就意味着不同的要求，我们需要用到不同的遍历顺序。

以完全背包（个数可以不限使用）为例，如果强调组合，我们可以先遍历物品，再遍历背包

如果强调排列，我们应该先遍历背包，再遍历物品

以力扣题目518.零钱兑换2为例：这就是一个组合问题，遇见组合问题我们一般用回溯法也比较好解决，但是此题只要计算有多少种方法即可，无需列出来有多少种，那么为减少时间和空间复杂度，用动态规划来解。

# 组合问题
def change(self, amount: int, coins: List[int]) -> int:
    dp = [0] * (amount + 1) # dp[j]表示金额为j时有dp[j]种换法
    dp[0] = 1	# 金额为0时默认有一种
    for i in range(len(coins)):  # 物品
        for j in range(coins[i], amount + 1):  # 背包体积
            dp[j] += dp[j - coins[i]]       # 相当于不用新的coin换的时候的换法+用新的coin换的时候的换发
    return dp[amount]
1
2
3
4
5
6
7
8

如果把遍历nums（物品）放在外循环，遍历target的作为内循环的话，举一个例子：计算dp[4]的时候，结果集只有 {1,3} 这样的集合，不会有{3,1}这样的集合，因为nums遍历放在外层，3只能出现在1后面！

以力扣题目377组合总和4.为例：这就是一个排列问题.

# 排列问题
def combinationSum4_1(self, nums: List[int], target: int) -> int:
    dp = [0] * (target + 1)  # dp[j] 表示组成目标数有dp[j]种
    dp[0] = 1
    for i in range(1, target+1):    # 先遍历背包
        for j in range(len(nums)):
            if i >= nums[j]:
                dp[i] += dp[i -nums[j]]
    return dp[target]
1
2
3
4
5
6
7
8
9

---

小总结：

​ 背包问题中此文列举了常见的0-1背包和完全背包问题。

​ 求解背包问题时，我们可以用二维数组（便于理解）也可以用一位数组（优化空间）

​ 在0-1背包中，我们用二维数组遍历顺序是可以任意的，但是用一维数组时，只能先遍历物品，然后再背包逆序遍历（目的是保证每次都只拿一个物品）

​ 在完全背包中，我们用的一维数组，且遍历顺序是可以任意的，因为这两种遍历顺序都保证了求解dp[j]时前面的j都已经被计算出来了。

​ 在完全背包的组合问题中，我们要先遍历背包，再遍历物品。

**中，我们用二维数组遍历顺序是可以任意的，但是用一维数组时，只能先遍历物品，然后再背包逆序遍历（目的是保证每次都只拿一个物品）

​ 在完全背包中，我们用的一维数组，且遍历顺序是可以任意的，因为这两种遍历顺序都保证了求解dp[j]时前面的j都已经被计算出来了。

​ 在完全背包的组合问题中，我们要先遍历背包，再遍历物品。

​ 在完全背包的排列问题中，我们要先遍历物品，再遍历背包。

部分文字参考：代码随想录