最適なナップザック ソリューションに含まれるアイテムを効率的に決定するにはどうすればよいでしょうか?

最適ナップサック解の要素の決定

指定されたナップサック アルゴリズムは、ビン パッキング問題の最適値を効率的に計算します。ただし、当面の課題は、この最適解を構成する要素を特定することです。

1.選択の追跡:

dp 行列の最適値を計算した後、バックトラックして選択された要素を決定できます。

dp_copy = dp;  // Copy the dp matrix for backtracking

int weight_idx = W;
int item_idx = n;

while (weight_idx > 0 && item_idx > 0):
    if dp_copy[weight_idx][item_idx] != dp_copy[weight_idx - items[item_idx - 1].getWeight()][item_idx - 1]:
        // Element 'item_idx' is included in the optimal solution
        weight_idx -= items[item_idx - 1].getWeight()
        item_idx -= 1

2.疑似コードの解釈:

• 最後のセルから最初のセルまで逆の順序で dp 行列を繰り返します。
• 現在のセルと現在のセルの違いを確認します。行列の上と左のセルは、対応するアイテムの重みに等しい。
• 等しい場合、そのセルの値に関連付けられたアイテムは次のようになります。
• さらにバックトラックするために、それに応じて重量インデックスとアイテム インデックスを調整します。

3.複雑さ:

このバックトラッキング アプローチには、O(W * n) の時間計算量が必要です。ここで、W はバッグの容量、n はアイテムの数です。行列内の各セルを 1 回反復し、定数時間の検索操作を実行します。

以上が最適なナップザック ソリューションに含まれるアイテムを効率的に決定するにはどうすればよいでしょうか?の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。