問題描述

這里我有使用背包算法計算最優值的代碼(裝箱 NP 難題):

Here I have code which calculates the optimal value using the knapsack algorithm (bin packing NP-hard problem):

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));
    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());
            }
            else
            {
                dp[w][j] = dp[w][j - 1];
            }
        }
    }
    return dp[W][n];
}

我還需要顯示包中包含的元素.我想創建一個數組來放置所選元素.那么問題來了，我可以在哪一步進行這個選擇呢?有沒有其他更有效的方法來確定哪些物品已被拿走?

I also need the elements included in the pack to be shown. I want to create an array to put the chosen elements. So the question is, in which step can I perform this selection? Is there any other more efficient way to determine which items have been taken?

我希望能夠知道為我提供最佳解決方案的項目，而不僅僅是最佳解決方案的價值.

I want to be able to know the items that give me the optimal solution, and not just the value of the best solution.

推薦答案

可以使用矩陣中的數據來獲取您從矩陣中打包的元素，而無需存儲任何其他數據.

Getting the elements you packed from the matrix can be done using the data from the matrix without storing any additional data.

偽代碼:

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

它背后的想法是迭代矩陣；如果重量差正好是元素的大小，則它在背包中.如果不是，則說明該物品不在背包中，請繼續.

The idea behind it is that you iterate the matrix; if the weight difference is exactly the element's size, it is in the knapsack. If it is not, the item is not in the knapsack, go on without it.

這篇關于如何使用背包算法(不僅是包的價值)找到包中的哪些元素?的文章就介紹到這了，希望我們推薦的答案對大家有所幫助，也希望大家多多支持html5模板網！