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

最適なナップサック ソリューションにおけるアイテムの決定

アイテムを最適に梱包して合計価値を最大化するナップサック アルゴリズムを前提として、この記事では追加の問題について説明します。最適なソリューションに含まれる特定の項目を特定するという課題です。

まず、ナップザック アルゴリズムの実装を詳しく調べます:

int Knapsack::knapsack(std::vector<Item>& items, int W) {...}

最適解に関係する項目を取得するには、計算された行列に保存されている情報を活用できます:

std::vector<vector<int>> dp(W + 1, std::vector<int>(n + 1, 0));

擬似コード:

line = W
i = n
while (i > 0):
  if dp[line][i] - dp[line - weight(i)][i-1] == value(i):
    // Item 'i' is in the knapsack
    i--
    line -= weight(i)
  else: 
    i--

この反復プロセスは、行列全体を反復処理します。重量の差がアイテムのサイズと一致する場合、そのアイテムは最適解の一部とみなされます。アイテムは検討から除外され、プロセスは続行されます。

この手法を採用することで、追加のデータ ストレージを必要とせずに、どのアイテムがナップザック内で最も価値のある組み合わせを構成するかを判断できます。このアプローチは効率的であるだけでなく、最適なソリューション構成についての貴重な洞察も提供します。

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