如何使用背包算法[而不仅仅是包的价值]找到包中的元素？

Question

我有一个代码,通过背包算法计算最佳值(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];
}

另外,我需要显示包含在内的元素.我想创建一个数组,添加一个元素.所以问题在于添加这个添加的步骤,或者可能还有其他更有效的方法吗？

问题:我希望能够了解为我提供最佳解决方案的项目,而不仅仅是最佳解决方案的价值.

PS.对不起我的英语,这不是我的母语.

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 

背后的想法:你迭代矩阵,如果重量差异正好是元素的大小,它就在背包中.
如果不是:该物品不在背包中,请在没有它​​的情况下继续.