javaのナップザック欲張りアルゴリズム

Question

ナップザック問題の非常に単純な貪欲アルゴリズムを書こうとしています。私の入力は2つの並列配列です。 1つの配列は項目の値を含み、もう1つの配列は重みを含みます。

私が作成しようとしている欲張りアルゴリズムは、次のようになります：どのアイテムが最高値であるかをチェックし、これをナップザックに入れます。次に、この項目の値をゼロに設定します。どのアイテムが最高の価値を持っているか再度確認し、ナップザックがまだそれを保持できる場合は、それをナップザックに入れてください。それを保持することができれば、値を再び0に設定して（値を入れた後に）再び最高値を探し始める。そのナップザックがこれ以上保持できない場合は、プログラムを終了してください。

私はそこに多くのより良い欲張りアルゴリズムがあることを知っていますが、これは私にとって非常に単純なものと思われ、私はこれを管理できると思います。私の問題は、最大値を見つけるために値配列全体を調べなければならないということです。それから私がそれを見つけたら、それをナップザックに入れ、その値をゼロに設定します。しかし問題は、新しい最高値アイテムを見つけてこれをナップザックに入れるためにforループに戻らなければならないということです。しかし、私はこれをどうやってやるのか分からない。

私はこれをJavaで書いています。

Answer 1

まず、ナップザックは唯一の値ではなく、最も高い比率の値/重みを使用して貪欲に解きます。

第2に、アイテムのリストを一度ソートして順を追って調べる場合、各ステップで最大値を検索する必要はありません。