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

Question

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

来自CSDojo的代码

Answer 1

这个解决方案之所以有效，是因为逻辑合理。让我们用文字表达这个逻辑:

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

def KS(n, C):

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

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

否则，如果该(第 n 个)项目的重量大于此容量( C )，则使用我们在没有此项目的情况下对此容量( C )可以获得的最佳结果。这就是 Max value for capacity C, using any of the first to (n-1)th items 的解决方案(请记住，当前计算正在查找 KS(n, C)，因此我们不允许使用列表中 n 之后的任何项目):

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

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

else:

如果我们不使用n第一项，与我们之前的可能性相同: Max value for capacity C, using any of the first to (n-1)th items 的解决方案:

  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 循环)。