下面记录一下背包问题的一些递推公式，包括 01 背包、完全背包（组合/排列）。

一、01 背包

每个物品只能选 0 次或 1 次。

状态定义：

• 一维 DP：

  • dp[j]：容量为 j 时的最大价值。

• 二维 DP：

  • dp[i][j]：前 i 个物品中，背包容量为 j 时的最大价值。

递推公式：

• 一维 DP：

  • dp[j] = max(dp[j], dp[j - <weight>] + <value>)

• 二维 DP：

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

遍历顺序：

• 外层物品，内层容量

  • 一维 DP 时，因为每个物品只能选一次，所以必须倒序遍历。如果正序遍历，会导致同一个物品被多次使用，相当于变成了完全背包

  // Kotlin
  val weights = intArrayOf(1, 3, 4)
  val values = intArrayOf(15, 20, 30)
  val bagSize = 4
  val dp = IntArray(bagSize + 1)
  
  for (i in weights.indices) {
      for (j in bagSize downTo weights[i]) {
          dp[j] = maxOf(dp[j], dp[j - weights[i]] + values[i])
      }
  }
  println(dp[bagSize])
  

  // Swift
  let weights = [1, 3, 4]
  let values = [15, 20, 30]
  let bagSize = 4
  var dp = [Int](repeating: 0, count: bagSize + 1)
  
  for i in 0..<weights.count {
      for j in stride(from: bagSize, through: weights[i], by: -1) {
          dp[j] = max(dp[j], dp[j - weights[i]] + values[i])
      }
  }
  print(dp[bagSize])
  

二、完全背包（组合）

物品可以无限次使用。

顺序无关，即 [1, 2] 和 [2, 1] 算一种。

状态定义：

• dp[j]：容量为 j 时，能取得的最大价值（或组合）。

递推公式：

• 求最大价值：
  • dp[j] = max(dp[j], dp[j - <weight>] + <value>)
• 求组合方案数：
  • dp[j] += dp[j - <weight>]

遍历顺序：

• 外层物品，内层容量

  • 每个物品可以被重复使用，所以内层的容量可以正序排列，正序可以确保使用该物品的所有组合都被正确累加。如果改为容量倒序，就会漏掉某些组合（如连续使用同一个物品的情况）。

  // Kotlin
  // 最大价值
  val weights = intArrayOf(1, 2)
  val values = intArrayOf(2, 3)
  val bagSize = 4
  val dp = IntArray(bagSize + 1)
  
  for (i in weights.indices) {
      for (j in weights[i]..bagSize) {
          dp[j] = maxOf(dp[j], dp[j - weights[i]] + values[i])
      }
  }
  println(dp[bagSize])
  

  // Swift
  // 组合方案数
  let weights = [1, 2]
  let bagSize = 4
  var dp = [Int](repeating: 0, count: bagSize + 1)
  dp[0] = 1
  
  for i in 0..<weights.count {
      for j in weights[i]...bagSize {
          dp[j] += dp[j - weights[i]]
      }
  }
  print(dp[bagSize])
  

三、完全背包（排列）

物品可以无限次使用。

顺序敏感，即 [1, 2] 和 [2, 1] 算两种不同的方案。

状态定义：

• dp[j]：容量为 j 时，能构成容量为 j 的最大排列数。

递推公式：

• dp[j] += dp[j - <weight>]

遍历顺序：

• 外层容量，内层物品，排列顺序敏感，相比组合，需要把背包和物品顺序颠倒。

  • 因为排列对顺序敏感，为了覆盖所有不同顺序的方案，必须先遍历容量，然后在每种容量下尝试以每个物品结尾，这样就可以覆盖所有排列方式。如果把物品遍历放到外层，就只能构成不重复的组合（顺序被固定）。

  // Kotlin
  // 排列方案
  val weights = intArrayOf(1, 2)
  val bagSize = 4
  val dp = IntArray(bagSize + 1)
  dp[0] = 1
  
  for (j in 1..bagSize) {
      for (i in weights.indices) {
          if (j >= weights[i]) {
              dp[j] += dp[j - weights[i]]
          }
      }
  }
  println(dp[bagSize])
  

  // Swift
  // 排列方案
  let weights = [1, 2]
  let bagSize = 4
  var dp = [Int](repeating: 0, count: bagSize + 1)
  dp[0] = 1
  
  for j in 1...bagSize {
      for i in 0..<weights.count {
          if j >= weights[i] {
              dp[j] += dp[j - weights[i]]
          }
      }
  }
  print(dp[bagSize])