擅长:python、mysql、java
<p>背包问题的基础是这样的:给定一组物品,每个物品都有一个值和一个重量,在给定的重量限制下找到最有价值的物品组合。在</p>
<p>这些都是你问题中的变量(顺便说一句:你朋友的命名习惯很糟糕)。在</p>
<p>此问题有两种终端情况:</p>
<ol>
<li><p>没有剩余项目</p></li>
<li><p>无剩余重量</p></li>
</ol>
<p>该计划如何解决这些问题?在</p>
<pre><code>if n == 0 or W == 0:
return 0
</code></pre>
<p>第二段代码是另一种情况</p>
<p>被测物品超过重量限制</p>
^{pr2}$
<p>这只意味着在删除当前测试项目的情况下尝试另一次背包算法迭代。在</p>
<p>这里的else块是拼图的最后一块</p>
<p>测试项目未超过重量限制</p>
<pre><code>else:
return max(val[n - 1] + knapSack(W - wt[n - 1], wt, val, n - 1),
knapSack(W, wt, val, n - 1))
</code></pre>
<p>这到底在说什么?最多返回两个选项:</p>
<ol>
<li><p>当前项目的值+再次执行背包算法得到的值(权重下限为W-wt[n-1]部分)和排除的项目值(n-1部分)。</p></li>
<li><p>不包括当前项目的背包算法和权重限制相同(假设当前项目很重,但价值不大,此选项可能会更高)。</p></li>
</ol>
<p>这是因为你实际上是在说接受这个项目的值,加入它,调整权重,看看什么是最好的剩余组合,或者不包括这个项目,看看什么是最好的剩余组合。这将测试所有可能的子选项组合。在</p>
<p>这整件事就是一个被称为<a href="https://en.wikipedia.org/wiki/Dynamic_programming" rel="nofollow noreferrer">Dynamic Programming</a>的范例。我建议你仔细阅读一下,找到一些类似这个问题的简单例子。一旦你摸索出解决这些问题的方法,理解它们就会变得容易得多。在</p>