背包问题-递归解法讲解
Knapsack Problem - Recursive solution explanation
我无法理解这种朴素的递归解决方案的工作原理和原因。如果我是第一次遇到这个问题，我会考虑（迭代地）对所有可能的组合进行详尽搜索，最后记录并返回最大值。有人可以解释一下这个解决方案吗？
来自 CSDojo 的代码
此方法可能会执行穷举搜索。
它是分支定界启发式算法的实现，其中 if-condition 会切断当前分支，因为它无法进一步增长。
没有那个切割算法为所有可能的子集构建完整的二叉树（tmp1和tmp2是选择-我们是否使用当前项目）
该解决方案基本上尝试将项目 n 放入（仅当它仍然适合时）或将其放在外面，然后尽可能好地放入剩余项目（递归调用).这给出了两个值 tmp1 和 tmp2。然后取其中的最大值。
这个解决方案之所以有效，是因为逻辑合理。让我们把这个逻辑写成文字：
容量 C 的最大值，使用第 n 项中的任何一项：
def KS(n, C):
如果我们没有使用任何物品或我们没有容量，那么我们的价值为零：
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] 添加到我们的解决方案中30=] 件物品，但容量为 C - current_weight，因此加上当前重量 w[n]，我们将提出仍保留容量 C:
的解决方案
tmp2 = v[n] + KS(n - 1, C - w[n])
选择较高的值：
result = max{ tmp1, tmp2 }
Return 我们当前参数的正确结果：
return result
递归可能有点违反直觉。调用 KS(n, C) 将生成一大堆对 "earlier" 参数的调用 n - 1、n - 2 等，并且容量较低，这使得这些调用看起来像是在发生 在 初始调用之后。但实际上 KS(n, C) 正在等待所有这些完成以回答它自己的计算，因此我们可以准确地说它发生在 "earlier" 参数调用之后。当参数值一致时，其中许多可能会重复，这就是缓存它们以加快例程的原因。
将 n, C 视为公式的 "search space" 也很有用。这意味着我们确实受限于 n * C 不同的参数组合。这就是为什么一些递归，比如背包，经常被列为 n 和 C 的迭代（例如嵌套 for 循环）。
我无法理解这种朴素的递归解决方案的工作原理和原因。如果我是第一次遇到这个问题，我会考虑（迭代地）对所有可能的组合进行详尽搜索，最后记录并返回最大值。有人可以解释一下这个解决方案吗？
来自 CSDojo 的代码
此方法可能会执行穷举搜索。
它是分支定界启发式算法的实现，其中 if-condition 会切断当前分支，因为它无法进一步增长。
没有那个切割算法为所有可能的子集构建完整的二叉树（tmp1和tmp2是选择-我们是否使用当前项目）
该解决方案基本上尝试将项目 n 放入（仅当它仍然适合时）或将其放在外面，然后尽可能好地放入剩余项目（递归调用).这给出了两个值 tmp1 和 tmp2。然后取其中的最大值。
这个解决方案之所以有效，是因为逻辑合理。让我们把这个逻辑写成文字：
容量 C 的最大值，使用第 n 项中的任何一项：
def KS(n, C):
如果我们没有使用任何物品或我们没有容量，那么我们的价值为零：
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] 添加到我们的解决方案中30=] 件物品，但容量为 C - current_weight，因此加上当前重量 w[n]，我们将提出仍保留容量 C:
tmp2 = v[n] + KS(n - 1, C - w[n])
选择较高的值：
result = max{ tmp1, tmp2 }
Return 我们当前参数的正确结果：
return result
递归可能有点违反直觉。调用 KS(n, C) 将生成一大堆对 "earlier" 参数的调用 n - 1、n - 2 等，并且容量较低，这使得这些调用看起来像是在发生 在 初始调用之后。但实际上 KS(n, C) 正在等待所有这些完成以回答它自己的计算，因此我们可以准确地说它发生在 "earlier" 参数调用之后。当参数值一致时，其中许多可能会重复，这就是缓存它们以加快例程的原因。
将 n, C 视为公式的 "search space" 也很有用。这意味着我们确实受限于 n * C 不同的参数组合。这就是为什么一些递归，比如背包，经常被列为 n 和 C 的迭代（例如嵌套 for 循环）。