0/1 C / C ++で分枝限定法を使用するナップザック？

アイデアは、貪欲なアプローチがフラクショナルナップサック問題の最良の解決策を提供するという事実を実装することです。

特定のノードがより良いソリューションを提供できるかどうかを確認するために、貪欲アプローチを実装する最適なソリューションを（ノードを介して）計算します。欲張り法自体によって計算された解がこれまでのところ最良以上である場合、ノードを介してより良い解を得ることができません。

完全なアルゴリズムを以下に示します-

• 貪欲アプローチを実装して上限を計算できるように、すべてのアイテムを単位重量あたりの値の比率の降順で並べ替えます。

• 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