动态规划2

作于：2025-06-21 23:42 ，最后更新于：2025-06-22 02:00 ，预计阅读时间 7 分钟

凌晨1点刚躺下快睡着的时候忽然想到了 01 背包问题的子问题是怎么拆分的，好像有点搞明白了动态规划的底层逻辑。

今天记录下。

01 背包问题

题目：

你有一个载重上限为 $W$ 的背包。现在有 $N$ 件物品，每件物品都有其重量 $w_i$ 和价值 $v_i$。你希望在不超过背包载重上限的前提下，选择一些物品放入背包，使得放入背包的物品总价值最大。每件物品只能选择放入或不放入一次。

请计算在给定背包容量下，能够获得的最大总价值。

输入参数：

背包容量 $W = 10$

物品列表：

物品重量 (w)价值 (v)
物品A26
物品B33
物品C410
物品D57

题解函数签名：

func SolveKnapsack(weights []int, values []int, capacity int) int {
	// 实现代码
}

使用自顶向下法分析 01 背包问题时，最关键的问题是 如何构造、遍历决策树 。知道了怎么遍历决策树，就能很自然地推导出问题的递归解。

决策树构建和遍历

先判断如何构建决策树，决策树实际就是 怎么遍历所有可能的组合。

graph TD
    S["容量10"]

    %% Item A (Weight: 2, Value: 6)
    S -- "放入物品A" --> A_T_8["容量8"]
    S -- "不放入物品A" --> A_NT_10["容量10"]

    %% Item B (Weight: 3, Value: 3)
    A_T_8 -- "放入物品B" --> B_T_5["容量5"]
    A_T_8 -- "不放入物品B" --> B_NT_8["容量8"]

    A_NT_10 -- "放入物品B" --> B_T_7["容量7"]
    A_NT_10 -- "不放入物品B" --> B_NT_10["容量10"]

    %% Item C (Weight: 4, Value: 10)
    B_T_5 -- "放入物品C" --> C_T_1["容量1"]
    B_T_5 -- "不放入物品C" --> C_NT_5["容量5"]

    B_NT_8 -- "放入物品C" --> C_T_4["容量4"]
    B_NT_8 -- "不放入物品C" --> C_NT_8["容量8"]

    B_T_7 -- "放入物品C" --> C_T_3["容量3"]
    B_T_7 -- "不放入物品C" --> C_NT_7["容量7"]

    B_NT_10 -- "放入物品C" --> C_T_6["容量6"]
    B_NT_10 -- "不放入物品C" --> C_NT_10["容量10"]

    %% Item D (Weight: 5, Value: 7)
    C_T_1 -- "放入物品D" --> D_T_neg4["容量-4"]
    C_T_1 -- "不放入物品D" --> D_NT_1["容量1"]

    C_NT_5 -- "放入物品D" --> D_T_0["容量0"]
    C_NT_5 -- "不放入物品D" --> D_NT_5["容量5"]

    C_T_4 -- "放入物品D" --> D_T_neg1["容量-1"]
    C_T_4 -- "不放入物品D" --> D_NT_4["容量4"]

    C_NT_8 -- "放入物品D" --> D_T_3["容量3"]
    C_NT_8 -- "不放入物品D" --> D_NT_8["容量8"]

    C_T_3 -- "放入物品D" --> D_T_neg2["容量-2"]
    C_T_3 -- "不放入物品D" --> D_NT_3["容量3"]

    C_NT_7 -- "放入物品D" --> D_T_2["容量2"]
    C_NT_7 -- "不放入物品D" --> D_NT_7["容量7"]

    C_T_6 -- "放入物品D" --> D_T_1["容量1"]
    C_T_6 -- "不放入物品D" --> D_NT_6["容量6"]

    C_NT_10 -- "放入物品D" --> D_T_5["容量5"]
    C_NT_10 -- "不放入物品D" --> D_NT_10["容量10"]

    %% Styles for negative capacity nodes
    style D_T_neg4 stroke:red,stroke-width:1px
    style D_T_neg1 stroke:red,stroke-width:1px
    style D_T_neg2 stroke:red,stroke-width:1px

语言描述就是：先访问放入不物品i的子节点；如果剩余空间足够放入物品i，再访问放入物品i的子节点。

可以很直观地写一个 traversal 实现这个决策树的遍历过程

var w []int // 物品占据的容量

// i 为物品下标，c 是背包剩余容量
func traversal(i,c int) {
  if i >= len(w) {
    return
  }

  // 不放物品i的分支
  traversal(i+1,c)
  if c-w[i]>=0{
    // 放物品i的分支
    traversal(i+1,c-w[i])
  }
}

这样一个 traversal 什么也没做，但是是动态规划递归解的一个很好的开始。

暴力搜索

原问题是让我们找出所有可能的排列组合中，价值最大的组合。

其实仔细看决策树就会发现，每个叶子节点代表了一种排列组合方式。在dfs到达一个叶子节点时，我们就得到了一个可行的物品组合，可以计算出一个物品组合的总价值。dfs遍历了所有叶子，也就是遍历了所有的物品组合。

这样一来，找最大价值的物品组合，就可以被描述为在这棵树里找到价值最大的那个叶子节点。我们就有了暴力搜索的解法。

var w []int // 物品占据的容量
var v []int // 物品价值

// 此函数任务是找出价值最大的叶子节点
// i 为物品下标，c 是剩余容量，selected 是选择的物品清单
// 返回考虑i件物品，剩余容量c 时能得到的最大价值
func dfs(i, c int, selected []int) int {
  // 叶子节点，所有的物品都决策完毕，计算物品组合的总价值
  if i == len(w) {
    var sum int
    for _, item := range selected {
      sum += v[item]
    }
    return sum
  }

  // 放/不放 物品i 分支的最大价值
  var a, b int

  // 不放物品i的分支
  a = dfs(i+1, c, selected)
  if w[i] <= c{
    // 放物品i的分支
    b = dfs(i+1, c-w[i], append(selected, i))
  }
  return max(a, b)
}

这个搜索过程会这样判断，比较两颗子树的最大价值，取较大者返回上一层，直到回到根节点，此时得到的最大价值就是整颗决策树里最大的那个叶子。

graph TD
    %% Define the final value of each path (leaf nodes)
    D_T_neg4["价值: 负无穷 (不可达)"]
    D_NT_1["价值: 16 (A+C)"]
    D_T_0["价值: 13 (A+B+D)"]
    D_NT_5["价值: 19 (A+B+C)"]
    D_T_neg1["价值: 负无穷 (不可达)"]
    D_NT_4["价值: 9 (A+D)"]
    D_T_3["价值: 13 (A+C+D)"]
    D_NT_8["价值: 9 (A)"]
    D_T_neg2["价值: 负无穷 (不可达)"]
    D_NT_3["价值: 10 (B+C)"]
    D_T_2["价值: 16 (B+D)"]
    D_NT_7["价值: 3 (B)"]
    D_T_1["价值: 17 (C+D)"]
    D_NT_6["价值: 10 (C)"]
    D_T_5["价值: 7 (D)"]
    D_NT_10["价值: 0"]

    %% Styles for unreachable paths
    style D_T_neg4 stroke:red,stroke-width:1px
    style D_T_neg1 stroke:red,stroke-width:1px
    style D_T_neg2 stroke:red,stroke-width:1px

    %% Define the maximum value propagated upwards
    C_T_1["决策出最大价值: 16"] --> D_T_neg4
    C_T_1["决策出最大价值: 16"] --> D_NT_1

    C_NT_5["决策出最大价值: 19"] --> D_T_0
    C_NT_5["决策出最大价值: 19"] --> D_NT_5

    C_T_4["决策出最大价值: 9"] --> D_T_neg1
    C_T_4["决策出最大价值: 9"] --> D_NT_4

    C_NT_8["决策出最大价值: 13"] --> D_T_3
    C_NT_8["决策出最大价值: 13"] --> D_NT_8

    C_T_3["决策出最大价值: 10"] --> D_T_neg2
    C_T_3["决策出最大价值: 10"] --> D_NT_3

    C_NT_7["决策出最大价值: 16"] --> D_T_2
    C_NT_7["决策出最大价值: 16"] --> D_NT_7

    C_T_6["决策出最大价值: 17"] --> D_T_1
    C_T_6["决策出最大价值: 17"] --> D_NT_6

    C_NT_10["决策出最大价值: 7"] --> D_T_5
    C_NT_10["决策出最大价值: 7"] --> D_NT_10

    B_T_5["决策出最大价值: 19"] --> C_T_1
    B_T_5["决策出最大价值: 19"] --> C_NT_5

    B_NT_8["决策出最大价值: 13"] --> C_T_4
    B_NT_8["决策出最大价值: 13"] --> C_NT_8

    B_T_7["决策出最大价值: 16"] --> C_T_3
    B_T_7["决策出最大价值: 16"] --> C_NT_7

    B_NT_10["决策出最大价值: 17"] --> C_T_6
    B_NT_10["决策出最大价值: 17"] --> C_NT_10

    A_T_8["决策出最大价值: 19"] --> B_T_5
    A_T_8["决策出最大价值: 19"] --> B_NT_8

    A_NT_10["决策出最大价值: 17"] --> B_T_7
    A_NT_10["决策出最大价值: 17"] --> B_NT_10

    S["最大总价值: 19"] --> A_T_8
    S["最大总价值: 19"] --> A_NT_10

但这还不是动态规划，因为我们没利用上它的最优子结构性质，也没有处理过程中的重叠子问题（决策树里包含很多重复的子组合，比如abcd,bcd,acd这样都包含cd物品的组合）。

动态规划(记忆化搜索法)

如果再仔细观察下，不难发现，任何层级中任何一个中间节点 N 的，它的最大价值只取决于自己的后继结点，它的前驱都是确定、不变的。

对于每个中间节点 N ，可以套用一个简化版本的公式： f(N) = max(f(left_child), f(right_child))，包括根节点。

这体现了 01 背包问题的 无后效性 和 最优子结构。

从这条简化的式子能很明显看出，如果一个全局最优路径（从根到最优叶子的路径）经过了某个中间节点，那么从这个中间节点到最优叶子的那段子路径，一定是该子问题（由中间节点定义）的最优解。。

由于这个最优子结构的性质，我们实际上不需要累计整个路径的决策价值，只需要逐级求解局部最优（已考虑i件物品，背包容量为c时的最大价值）返回即可：

f(i,c) = max(w[i] <= c ? v[i] + f(i+1, c-w[i]) : 0, f(i+1, c))

其中 i 是物品下标，c 是剩余容量。当 i 不存在时，f(i,c)=0。

这样我们就得到了一个看起来比较 dp 递归解。而 dp 递归解还要处理重叠子问题，也就是搜索过程会遍历到一模一样的子树时。

我们再加上 memo，就得到了动态规划的记忆化搜索算法（递归解）

var memo map[int]map[int]int
var w []int // 物品占据的容量
var v []int // 物品价值

// 此函数递归计算局部价值最大化路径，汇总成全局价值最大化路径。
// i 为物品下标，c 是背包剩余容量
func dfs(i, c int) int {
  if i >= len(w) {
    return 0
  }

  if memo[i][c] > 0 {
    return memo[i][c]
  }

  var a, b int
  a = dfs(i+1, c)
  if w[i] <= c {
    b = v[i] + dfs(i+1,c-w[i])
  }
  memo[i][c] = max(a, b)
  return memo[i][c]
}

动态规划（填表法）

var w []int
var v []int

func solve() int {
	numItems := len(weights)
	// dp[i][j] 表示：考虑前i件物品，背包容量为j时，能够获得的最大价值
	// dp 数组的大小为 (numItems + 1) x (capacity + 1)
	// 额外的一行一列用于处理“0件物品”或“0容量”的边界情况
	dp := make([][]int, numItems+1)
	for i := range dp {
		dp[i] = make([]int, capacity+1)
	}

	// 无需初始化，go 默认初始化为 0 了。

	// 填充DP表
	// i 从 1 到 numItems，表示当前考虑的是第 i 件物品 (对应 weights[i-1] 和 values[i-1])
	for i := 1; i <= numItems; i++ {
		// j 从 1 到 capacity，表示当前背包的容量
		for j := 1; j <= capacity; j++ {
			// 当前物品的重量和价值 (注意索引偏移：dp表中的i对应物品数组中的i-1)
			currentWeight := weights[i-1]
			currentValue := values[i-1]
			// 情况1: 当前物品i无法放入背包 (重量超过当前容量)
			if currentWeight > j {
				dp[i][j] = dp[i-1][j] // 价值等于不放这件物品的价值
			} else {
				// 情况2: 当前物品i可以放入背包
				// 选项A: 不放当前物品i
				a := dp[i-1][j]
				// 选项B: 放当前物品i
				// 价值 = 当前物品的价值 + 剩余容量下（前i-1件物品）能获得的最大价值
				b := currentValue + dp[i-1][j-currentWeight]
				// 取这两种情况的最大值
				dp[i][j] = max(a, b)
			}
		}
	}
	// 最终结果存储在 dp[numItems][capacity]
	return dp[numItems][capacity]
}

填表法其实也挺暴力的，它不会管实际决策树里在叶子节点会遇到哪些剩余背包容量，而是直接从0到最大容量全部填完，对每一种可能的剩余背包容量情况都做了判断。

填表法内部是模拟了递归的栈，dp[i-1][j-currentWeight] 就是递归法代码对应 dfs 的参数返回的值。

再观察下就会发现这个问题只依赖上一级的最优解，所以 dp 数组是可以优化成一个一维数组的。就不展开了。

总结

01 背包其实搞懂构建决策树和怎么深度优先遍历就解决一半问题了。剩下一半明确局部最优的解法也差不多了。

遗憾的是还是不明白怎么证明决策树中间节点N到最大价值的叶子L一定是局部最优。

/go/ /动态规划/ /01背包问题/