4

すべての利益が 1 に等しい場合のナップザック問題のバリエーションがあります。古典的な離散 (0-1) ナップザック問題よりもはるかに速く解決できるようですが、どうすればよいでしょうか? 貪欲なアルゴリズムだけが機能しますか (反復ごとに最小重量のオブジェクトをナップザックに入れます)?

4

1 に答える 1

3

そう思うはずです。

直感的に、すべての利益が 1 に等しいとすると、利益の面では、どのアイテムを選択するかに関係なく、できる限り多くのアイテムが必要になります。貪欲なアルゴリズムは、まさにそれを提供します。

于 2010-12-04T10:26:40.647 に答える