algorithm - 背包问题-递归解法讲解

Question

我无法理解这种朴素的递归解决方案的工作原理和原因。如果我是第一次遇到这个问题，我会考虑(迭代地)对所有可能的组合进行详尽搜索，最后记录并返回最大值。有人可以解释一下这个解决方案吗？

来自 CSDojo 的代码

Answer 1

此解决方案之所以有效，是因为其逻辑合理。让我们把这个逻辑写成文字:

容量 C 的最大值，使用第一个到第 n 个项目中的任何一个:

def KS(n, C):

如果我们没有使用任何元素或我们没有容量，那么我们的值(value)为零:

If n == 0 or C == 0:
  result = 0

否则如果这个(第n)项的重量大于这个容量(C)，使用我们能得到的这个容量的最好结果(C) 没有这个项目。这是容量 C 的最大值的解决方案，使用第一个到第 (n-1) 个项目中的任何一个(请记住，当前计算正在寻找 KS(n, C) 所以我们不允许使用列表中第 n 之后的任何项目):

else if w[n] > C:
  result = KS(n - 1, C)

否则，让我们决定是否应该使用这个项目:

else:

如果我们不使用第 n 项，这与我们之前的可能性相同:容量 C 的 Max value 的解决方案，使用第一个到 (n- 1)项:

  tmp1 = KS(n - 1, C)

如果我们确实使用它，因为当前计算正在寻找容量 C 的解决方案，让我们将当前值 v[n] 添加到我们的解决方案中使用任何先前的 n-1 项目，但容量为 C - current_weight 以便连同当前重量 w[n]，我们将展示仍然保留容量 C 的解决方案:

  tmp2 = v[n] + KS(n - 1, C - w[n])

选择较高的值:

  result = max{ tmp1, tmp2 }

返回我们当前参数的正确结果:

return result 

递归可能有点违反直觉。调用 KS(n, C) 将生成对“较早”参数 n - 1、n - 2 等的一大堆调用。和较低的容量，这使得这些调用看起来像是在初始调用之后发生的。但实际上 KS(n, C) 正在等待所有这些完成以回答它自己的计算，因此我们可以准确地说它发生在“较早的”参数调用之后。当参数值一致时，其中许多可能会重复，这就是缓存它们以加快例程的原因。

将 n, C 视为公式的“搜索空间”也很有用。这意味着我们实际上仅限于 n * C 不同的参数组合。这就是为什么一些递归，如背包，通常被列为 n 和 C 的迭代(例如，嵌套的 for 循环)。