Coursera の Tim RoughGarden による Algorithms-II コースで、0-1 ナップザック問題を説明しながら、彼は次のように言及し、私は引用します
「ナップザックの容量から Wn を取り除くことで、残りの部分問題を見る前に、アイテム N が必要になった場合にバッファを確保していることになります。これにより、N を元に戻したときに実現可能であることがわかります。これは、パスの最後から 2 番目の頂点を削除することに類似しており、N 番目の頂点を独立集合の問題に戻す際の実現可能性を確保するためのバッファーとして使用されます。」
このナップザック問題と最大独立集合問題の比較を説明してください。それらはどのように相互に関連していますか。探しても
しかし、両者の間に関係は見つかりませんでした。