Java でのナップザック アルゴリズムの実装方法の分析例

黄舟
リリース: 2017-08-23 10:46:54
オリジナル
1771 人が閲覧しました

この記事は主に Java でのナップサック アルゴリズム (0-1 ナップサック問題) の実装に関する簡単な議論を紹介しています。編集者はそれが非常に優れていると考えたので、参考として共有します。編集者をフォローして見てみましょう

0-1 ナップサック問題

ナップサック問題は、組み合わせ最適化の NP 完全問題です。この問題は、次のように説明できます。アイテムのセットが与えられ、各アイテムには独自の重量と価格があり、制限された合計重量の範囲内で、アイテムの合計価格が最高になるように選択するにはどうすればよいですか。この問題の名前は、特定のバックパックに入れるのに最も適切なアイテムを選択する方法に由来しています。

これはバックパックの最も基本的な質問です。その特徴は、各タイプのアイテムが 1 つだけあり、付けるかどうかを選択できることです。

副問題を使用して状態を定義します。つまり、f[i][v] は、容量 v のバックパックに最初の i 個のアイテムを入れることで取得できる最大値を表します。この場合、状態遷移方程式は次のようになります:

f[i][v]=max{ f[i-1][v], f[i-1][v-w[i]]+v[i] }。


りー

以上がJava でのナップザック アルゴリズムの実装方法の分析例の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。

ソース:php.cn
このウェブサイトの声明
この記事の内容はネチズンが自主的に寄稿したものであり、著作権は原著者に帰属します。このサイトは、それに相当する法的責任を負いません。盗作または侵害の疑いのあるコンテンツを見つけた場合は、admin@php.cn までご連絡ください。
人気のチュートリアル
詳細>
最新のダウンロード
詳細>
ウェブエフェクト
公式サイト
サイト素材
フロントエンドテンプレート