如何使用背包算法(不仅是包的价值)找到包中的哪些元素?

2021-12-06 00:00:00 algorithm dynamic-programming c++ knapsack-problem

这里我有使用背包算法计算最优值的代码(装箱 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.

相关文章