在Tim Roughgarden关于Coursera的算法II课程中，在解释0-1背包问题时，他提到了以下内容，我引用了
“通过从背包容量中去掉Wn，在我们研究剩余子问题之前，我们实际上是为N项预留了一个缓冲区，如果我们需要的话，这就是我们如何知道当我们将N重新放入这个解决方案s*中时我们是可行的这类似于删除路径的倒数第二个顶点，同样作为缓冲区，以确保我们将第n个顶点包含回独立集问题中时的可行性。”
请解释背包问题与最大独立集问题的比较。它们是如何相互关联的。即使我搜查过
http://en.wikipedia.org/wiki/Independent_set_(graph_theory)
但找不到两者之间的任何联系。
最佳答案
根据我对这段代码的理解，作者试图解释如何从当前问题中获取较小的子问题。
在背包的情况下，他意味着，例如给定权重{5, 3, 7, 1, 4}和大小15的背包，可以通过选择第一个项并查看剩余空间来创建子问题也就是说，剩下的问题是解决{3, 7, 1, 4}和10背包大小的背包问题（注意，这只是解决方案的一部分）。
在独立设置中，你有类似的东西给定顶点{A, B, C, D, E}和边{(A, B), (A, D), (B, C), (C, D), (C, E), (D, E)}，可以通过选择第一个顶点（A）并查看剩余的图来创建子问题。需要移除A的所有邻居，所以剩下的问题是找到一组独立的顶点{C, E}和边{(C, E)}。
不过，我必须说，这种相似性是相当大的延伸。