すべての利益が1に等しいナップザック問題

Question

すべての利益が1に等しい場合、ナップザック問題のバリエーションがあります。これは古典的な離散（0-1）ナップザック問題よりもはるかに高速に解決できるようですが、どうですか？ちょうど欲張りなアルゴリズムの仕事（各反復で最小の重さを持つオブジェクトをナップザックに入れますか？）

Answer 1

私はそう考えるべきです。

直感的に言えば、すべての利益が等しいとすれば、利益面ではあなたが選択する項目に無関心です。できるだけ多くのものを必要とします。貪欲なアルゴリズムはあなたにそれを正確に与えるでしょう。