基于归纳法证明背包问题动态规划递推式的最优性

嘿，我太懂你卡在归纳步骤的那种纠结了——数学归纳法和动态规划结合的时候，递推环节的逻辑总是需要把“最优子结构”这个点掰透才行。咱们一步步来，把这个证明理得明明白白！

首先先统一一下符号定义，避免歧义：

• Opt(i,w)：表示考虑前i个物品、背包容量为w时的最优解（这里按你给出的递推式，默认物品i的“价值”就是它的重量wᵢ，目标是最大化总重量）
• wᵢ：第i个物品的重量

基础情况（i=1） #

你已经想到这一步了，咱们快速过一遍确认：

• 当w < w₁：背包装不下第一个物品，最优解就是0，对应Opt(0,w)=0（默认前0个物品的最优解为0），符合Opt(1,w)=Opt(0,w)。
• 当w ≥ w₁：最优解就是装入第一个物品，总重量为w₁，对应max(Opt(0,w)=0, Opt(0,w-w₁)+w₁=0+w₁)，完全匹配递推式。
  基础情况成立。

归纳步骤（核心环节） #

我们先做归纳假设：对于所有的k < i，以及任意的背包容量w，Opt(k,w)都能正确给出考虑前k个物品、容量w时的最优解。现在要证明这个结论对k=i同样成立。

我们分两种情况讨论：

情况1：w < wᵢ #

此时背包的容量根本装不下第i个物品，那么考虑前i个物品的最优解，本质上和只考虑前i-1个物品的最优解完全一致——因为第i个物品没有被选入的可能。根据归纳假设，Opt(i-1,w)是前i-1个物品的最优解，因此Opt(i,w)=Opt(i-1,w)，递推式成立。

情况2：w ≥ wᵢ #

这时候我们有两种可选策略，递推式取的是两者的最大值，我们需要证明这个最大值就是真正的最优解：

1. 不选第i个物品：此时最优解就是前i-1个物品在容量w下的最优解，也就是Opt(i-1,w)——这是归纳假设直接保证正确的。
2. 选第i个物品：如果选择装入第i个物品，那么剩余可用容量就是w - wᵢ，我们需要在前i-1个物品中找到容量w - wᵢ下的最优解，再加上第i个物品的重量wᵢ。根据归纳假设，Opt(i-1, w - wᵢ)是前i-1个物品在该剩余容量下的最优解，因此这种策略的总重量是Opt(i-1, w - wᵢ) + wᵢ。

现在关键要证明：前i个物品的最优解必然是这两种策略中的最大值。我们用反证法来推导：
假设存在一个比这两个值都大的最优解，分两种子情况看：

• 如果这个最优解没有选第i个物品，那它的总重量应该等于Opt(i-1,w)，但我们假设它更大，这直接和归纳假设中Opt(i-1,w)是前i-1个物品的最优解矛盾。
• 如果这个最优解选了第i个物品，那它的总重量等于“前i-1个物品在容量w - wᵢ下的重量”加上wᵢ，但我们假设它比Opt(i-1, w - wᵢ) + wᵢ更大，这意味着前i-1个物品在容量w - wᵢ下存在一个比Opt(i-1, w - wᵢ)更优的解，同样和归纳假设矛盾。

因此不存在这样的“更优解”，所以Opt(i,w)必然等于两种策略的最大值，也就是max{Opt(i-1,w), Opt(i-1, w - wᵢ) + wᵢ}，递推式成立。

结论 #

基础情况成立，且如果对i-1成立则对i也成立，因此根据数学归纳法，对于所有的物品数量i和背包容量w，这个动态规划递推式都能给出背包问题的最优解。

内容的提问来源于stack exchange，提问作者WartSemola