c++ - 如何使用背包算法[而不仅仅是包的值(value)]找到包中的哪些元素？

Question

这里我有使用背包算法计算最优值的代码(装箱 NP 难题):

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];
}

我还需要显示包中包含的元素。我想创建一个数组来放置所选元素。所以问题是，我可以在哪一步执行这个选择？有没有其他更有效的方法来确定哪些元素已被拿走？

我希望能够知道给我最佳解决方案的项目，而不仅仅是最佳解决方案的值(value)。

Answer 1

可以使用矩阵中的数据来获取您从矩阵中打包的元素，而无需存储任何额外的数据。

伪代码:

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 

它背后的想法是你迭代矩阵；如果重量差异恰好是元素的大小，则它在背包中。如果不是，则该元素不在背包中，继续没有它。