分岐限定法を使用した C/C++ での 0/1 ナップザック問題の実装

アイデアは、貪欲な方法が分数ナップザック問題に対する最良の解決策を提供するという事実を認識することです。

特定のノードがより良いソリューションを提供できるかどうかを確認するために、貪欲なアプローチを実装して最適なソリューションを (ノードごとに) 計算します。貪欲な方法自体がこれまでの最良の解よりも多くの解を計算する場合、ノードを通じてより良い解を得ることができません。

完全なアルゴリズムは次のとおりです。 -

• すべてのアイテムを単位重量比の値の降順に並べ替えて、貪欲なアルゴリズムを使用して上限を計算できるようにします。方法。

• 最大利益を初期化します (例: maxProfit = 0

• 空のキュー Q を作成します)。

• 意思決定仮想ノードはツリーを作成し、それを Q に挿入またはキューに入れます。仮想ノードの利益と重みは 0 です。

• Q が空でない場合、または空の場合は、次の操作を実行します。

  • Q でプロジェクトを作成しました。抽出項目をuとする。

  • 次のレベルのノードの利益を計算します。利益が maxProfit よりも高い場合は、maxProfit を変更します。

  • 次のレベルのノードの制限を計算します。バウンドが maxProfit より大きい場合、次のレベルのノードを Q に追加します。

  • 次のレベルのノードが考慮されない、またはソリューションの一部として考慮されず、次のレベルのレベルでキューにノードを追加しますが、重みと利益は処理されていません。または、次のレベルのノードを検討してください。

以下の図 -

入力

// First thing in every pair is treated as weight of item
// and second thing is treated as value of item
Item arr1[] = {{2, 40}, {3.14, 50}, {1.98, 100}, {5, 95}, {3, 30}};
Knapsack Capacity W1 = 10

出力

The maximum possible profit = 235

以上が分岐限定法を使用した C/C++ での 0/1 ナップザック問題の実装の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。