背包问题-递归解决方案说明 [英] Knapsack Problem - Recursive solution explanation

问题描述

我无法理解这种幼稚的递归解决方案的工作方式和原因.如果是初次遇到此问题，我想考虑使用所有可能的组合(反复)进行详尽的搜索，最后记录并返回最大值.有人可以解释一下该解决方案吗?

I’m having trouble understanding how and why this naive recursive solution works. If I was given this problem for the first time, I’d think of doing an exhaustive search (iteratively) with all possible combinations, recording and returning the maximum value at the end. Can someone please explain this solution?

来自Csjo的代码

推荐答案

此解决方案有效，因为逻辑是合理的.让我们把这种逻辑写成文字:

This solution works because the logic is sound. Let's put that logic into words:

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

Max value for capacity C, using any of the first to nth items:

def KS(n, C):

如果我们不使用任何物品或没有容量，那么我们的值为零:

If we're not using any items or we have no capacity, then we have zero 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个之后使用任何项目)

Otherwise if the weight of this (the nth) item is greater than this capacity (C), use the best result we can get for this capacity (C) without this item. That's the solution for Max value for capacity C, using any of the first to (n-1)th items (remember that the current calculation is looking for KS(n, C) so we're not permitted to use any items after the nth in the list):

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

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

Otherwise, let's decide if we should use this item or not:

else:

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

If we don't use the nth item, that's the same as our previous possibility: the solution for Max value for capacity C, using any of the first to (n-1)th items:

  tmp1 = KS(n - 1, C)

如果我们确实使用它，由于当前计算正在寻找容量C的解决方案，因此让我们使用以前的n-1项(但具有容量)将当前值v[n]添加到我们的解决方案中C - current_weight，以便与当前的重量w[n]一起，提出仍保留容量C的解决方案:

If we do use it, since the current calculation is looking for a solution for capacity C, let's add the current value, v[n], to our solution using any of the previous n-1 items, but with capacity C - current_weight so that together with the current weight, w[n], we will be presenting the solution that still leaves capacity C:

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

选择较高的值:

  result = max{ tmp1, tmp2 }

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

Return the correct result for our current parameters:

return result 

递归可能有点违反直觉.调用KS(n, C)会生成对较早的"参数n - 1，n - 2等的一大堆调用，并且容量较低，这使得这些调用似乎在最初的之后发生称呼.但是实际上KS(n, C)正在等待所有这些完成以回答其自己的计算，因此我们可以准确地说出它是在更早的"参数调用之后发生的.当参数值重合时，它们中的许多可能会重复出现，这就是为什么对它们进行缓存以加快例程效率的原因.

Recursion can be a little counter-intuitive. Calling KS(n, C) will generate a whole bunch of calls to "earlier" parameters n - 1, n - 2, etc., and lower capacities, which makes it seem like those calls are happening after the initial call. But actually KS(n, C) is waiting for all those to complete in order to answer its own calculation so we can accurately say it's happening after the "earlier" parameter calls. And many of them might get repeated, when the parameter values coincide, which is why it can be useful to cache them to speed up the routine.

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

It can also be useful to consider n, C as the "search space" of the formulation. That means we're really restricted to n * C different combinations of parameters. That's why some recursions, like knapsack, are often tabulated as an iteration over n and C (nested for loops, for example).

这篇关于背包问题-递归解决方案说明的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！