动态规划经典问题学习记录

0-1 背包

问题描述

有 $n$ 个物品，第 $i$ 个物品的体积为 $w[i]$ ，价值为 $v[i]$ ，每个物品最多选一次，求体积和不超过 $capacity$ 时的最大价值和。

通过回溯去思考解题思路

  1. 先去思考当前的操作，即枚举第 $i$ 个物品选与不选：
    • 不选，剩余容量不变。
    • 选，剩余容量减少 $w[i]$ 。
  2. 递归到子问题，在剩余容量为 $c$ 时，从前 $i$ 个物品中得到的最大价值和。
  3. 下一个递归子问题：
    • 不选，在剩余容量为 $c$ 时，从前 $i-1$ 个物品中得到的最大价值和。
    • 选，在剩余容量为 $c-w[i]$ 时，从前 $i-1$ 个物品中得到的最大价值和。

最终得到的递归公式：$dfs(i,c) = max(dfs(i-1, c),dfs(i-1, c-w[i])+v[i])$

对应的代码就是：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

def zero_one_backpack(capacity: int, w: List[int], v: List[int]) -> int:
  n = len(w)
  
  @cache  # 记忆化搜索数组
  def dfs(i: int, c: int) -> int:
    # 跳出递归条件
    if i < 0:
      return 0
    # 容量不足时
    if c < w[i]:
      return dfs(i-1, c)
    # 将问题进一步分解
    return max(dfs(i-1, c), dfs(i-1, c-w[i]) + v[i])
  
  return dfs(n-1, capacity)

以上就是 0-1 背包的“至多装 capacity”的递归+记忆化搜索形式，其实也可以写成递推式：$dp[i][c] = max(dp[i-1][c],dp[i-1] [c-w[i]]+v[i])$

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

def zero_one_backpack(capacity: int, w: List[int], v: List[int]) -> int:
    n = len(w)
    # 初始化 dp 数组，大小为 (n+1) x (capacity+1)
    dp = [[0] * (capacity + 1) for _ in range(n + 1)]
    
    # 填充 dp 数组
    for i in range(1, n + 1):
        for c in range(capacity + 1):
            if c < w[i - 1]:
                # 如果当前容量不足以放入第 i 个物品，则只能选择不放入
                dp[i][c] = dp[i - 1][c]
            else:
                # 选择放入或不放入第 i 个物品，取较大值
                dp[i][c] = max(dp[i - 1][c], dp[i - 1][c - w[i - 1]] + v[i - 1])
    
    # 返回前 n 个物品在容量为 capacity 时的最大价值
    return dp[n][capacity]

0-1 背包变体

常见的变体有三种：

  • 至多装 capacity，求方案数/最大价值和。
  • 恰好装 capacity，求方案数/最大或最小价值和。
  • 至少装 capacity，求方案数/最小价值和。

经典的 0-1 背包原型属于第一种，接下来看第二种。

题目来自 494. 目标和 - 力扣（LeetCode） ：

  • 给你一个非负整数数组 nums 和一个整数 target 。

    向数组中的每个整数前添加 '+' 或 '-' ，然后串联起所有整数，可以构造一个 表达式 ：

    • 例如，nums = [2, 1] ，可以在 2 之前添加 '+' ，在 1 之前添加 '-' ，然后串联起来得到表达式 "+2-1" 。

    返回可以通过上述方法构造的、运算结果等于 target 的不同 表达式 的数目。

把问题转化为背包问题：

  • 假设我们选择一些数字添加 +，另一些添加 -。
  • 设 sum(+) 为所有添加 + 的数字之和，sum(-) 为所有添加 - 的数字绝对值之和。
  • 根据题意，有：sum(+) - sum(-) = target。
  • 又因为 sum(+) + sum(-) = sum(nums)，解得 sum(+) = (sum(nums) + target) / 2 。
  • 因此，问题转化为：从 nums 中选出一些数字，使得它们的和等于 (sum(nums) + target) / 2。这是一个典型的 0-1 背包问题。

得递归公式：$dfs(i, c) = dfs(i - 1, c) + dfs(i - 1, c - nums[i])$ ，这里的加法表示互斥条件，表示方案数两者之和。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

def findTargetSumWays(nums: List[int], target: int) -> int:
    # 计算目标和
    s = sum(nums) - abs(target)
    # 如果 s 为负数或奇数，则无解
    if s < 0 or s % 2:
        return 0
    # 目标容量
    capacity = s // 2

    # 记忆化搜索
    @cache
    def dfs(i: int, c: int) -> int:
        # 递归终止条件：如果遍历完所有数字
        # 这里 c == 0 表示满足“恰好”这个条件，否则表示没有找到
        if i < 0:
            return 1 if c == 0 else 0
        # 如果当前容量不足以放入 nums[i]
        if c < nums[i]:
            return dfs(i - 1, c)
        # 选择是否放入 nums[i]
        return dfs(i - 1, c) + dfs(i - 1, c - nums[i])

    # 返回结果
    return dfs(len(nums) - 1, capacity)

写成递推式就是：

 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

def findTargetSumWays(nums: List[int], target: int) -> int:
    # 计算目标和
    s = sum(nums) - abs(target)
    # 如果 s 为负数或奇数，则无解
    if s < 0 or s % 2:
        return 0
    # 目标容量
    capacity = s // 2
    
    n = len(nums)
    # n 行，capacity 列
    dp = [[0] * (capacity + 1) for _ in range(n + 1)]
    dp[0][0] = 1

    for i, v in enumerate(nums):
      for c in range(capacity + 1):
        # 如果当前容量不足以放入 nums[i]
        if c < v:
            dp[i + 1][c] = dp[i][c] 
        # 选择是否放入 nums[i]
      	else:
        	dp[i+1][c] = dp[i][c] + dp[i][c-v]

    # 返回结果
    return dp[n][capacity]

完全背包

问题描述

有 $n$ 个物品，第 $i$ 个物品的体积为 $w[i]$ ，价值为 $v[i]$ ，每个物品可无限次重复选，求体积和不超过 $capacity$ 时的最大价值和。

通过回溯思考解题思路

  1. 先去思考当前的操作，即枚举第 $i$ 个物品选与不选：
    • 不选，剩余容量不变。
    • 选，剩余容量减少 $w[i]$ 。
  2. 递归到子问题，在剩余容量为 $c$ 时，从前 $i$ 个物品中得到的最大价值和。
  3. 下一个递归子问题：
    • 不选，在剩余容量为 $c$ 时，从前 $i-1$ 个物品中得到的最大价值和。
    • 选，在剩余容量为 $c-w[i]$ 时，从前 $i$ 个物品中得到的最大价值和。注意，这里变成了前 $i$ 个，而不是 0-1 背包的前 $i-1$ 个。

最终得到的递归公式：$dfs(i,c) = max(dfs(i-1, c),dfs(i, c-w[i])+v[i])$ ，对应代码：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

def unbounded_backpack(capacity: int, w: List[int], v: List[int]) -> int:
  n = len(w)
  
  @cache  # 记忆化搜索数组
  def dfs(i: int, c: int) -> int:
    # 跳出递归条件
    if i < 0:
      return 0
    # 容量不足时
    if c < w[i]:
      return dfs(i-1, c)
    # 将问题进一步分解
    return max(dfs(i-1, c), dfs(i, c-w[i]) + v[i])
  
  return dfs(n-1, capacity)

完全背包变体

完全背包的变体与 0-1 背包的变体类型完全一致，也是三种。下面是第二种，“恰好”型完全背包问题。

题目来自 322. 零钱兑换 - 力扣（LeetCode） ：

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

    计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回 -1 。

    你可以认为每种硬币的数量是无限的。

转换成背包问题的话，这里的 amount 就是背包容量，而最少的硬币个数就是最小的价值和，这里的价值可以用 1 表示，所以得到递归公式：$dfs(i, c) = min(dfs(i-1, c), dfs(i, c-w[i])+1)$ 。

以下是递归式代码：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

def coinChange(coins: List[int], amount: int) -> int:
  n = len(coins)
  
  @cache
  def dfs(i: int, c: int) -> int:
    if i < 0:
      return 0 if c == 0 else inf
    
    if c < coins[i]:
      return dfs(i-1, c)
    return min(dfs(i-1, c), dfs(i, c-coins[i]) + 1)
  
  ans = dfs(n-1, amount)
  
  return ans if ans < inf else -1

改成递推式则为：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

def coinChange(coins: List[int], amount: int) -> int:
  n = len(coins)
  
  dp = [[inf] * (amount + 1)for _ in range(n + 1)]
  dp[0][0] = 0
  
  for i, v in enumerate(coins):
    for c in range(amount + 1):
      if c < v:
        dp[i+1][c] = dp[i][c]
      else:
        dp[i+1][c] = min(dp[i][c], dp[i+1][c-v]+1)
   
  ans = dp[n][amount]
  return ans if ans < inf else -1