我們如何確定最佳背包解決方案中包含的具體物品？

確定最優背包解決方案中的元素

背包演算法是NP-hard 裝箱問題的解決方案，可計算最優背包演算法從一組容量有限的物品中可以獲得的價值。然而，它常常讓用戶想知道哪些特定項目有助於這個最佳解決方案。

為了解決這個問題，我們可以修改背包演算法來追蹤最佳化過程中選擇的元素。這提供了一種直接的方法來識別構成最佳解決方案的項目，而不是僅僅依賴解決方案的值。

方法：

1. 建立一個附加的矩陣selected，其中selected[w][j] 表示索引j-1 處的元素是否在容量w處被選擇。
2. 初始化選擇的矩陣為 0。
3. 在背包演算法中，更新dp[w][j] 時，如果選擇了items[j-1]（dp[ w][j] = dp[w - items[j-1]. getWeight()][j-1] items[j-1].getWeight())表示該元素已被
4. 確定最佳值後，追蹤所選矩陣以識別所選的特定項目。

偽代碼：

int Knapsack::knapsack(std::vector<Item>& items, int W)
{
    size_t n = items.size();
    std::vector<std::vector<int>> dp(W + 1, std::vector<int>(n + 1, 0));
    std::vector<std::vector<int>> selected(W + 1, std::vector<int>(n + 1, 0));
    for (size_t j = 1; j <= n; j++)
    {
        for (int w = 1; w <= W; w++)
        {
            if (items[j-1].getWeight() <= w)
            {
                dp[w][j] = std::max(dp[w][j-1], dp[w - items[j-1].getWeight()][j-1] + items[j-1].getWeight());
                selected[w][j] = (dp[w][j] != dp[w][j-1]);
            }
            else
            {
                dp[w][j] = dp[w][j - 1];
            }
        }
    }

    // Identify selected items
    std::vector<int> takenItems;
    int line = W;
    int i = n;
    while (i > 0) {
      if (selected[line][i]) {
        takenItems.push_back(items[i-1].getIndex()); // Index of item taken
        line -= items[i-1].getWeight();
      }
      i--;
    }

    return dp[W][n];
}

這種增強的背包演算法不僅可以識別最佳值，還可以識別有助於該最佳值的特定元素解決方案。

以上是我們如何確定最佳背包解決方案中包含的具體物品？的詳細內容。更多資訊請關注PHP中文網其他相關文章！