如何找到哪些元素是囊中，用背包算法[不仅包的价值] [英] How to find which elements are in the bag, using Knapsack Algorithm [and not only the bag's value]?

问题描述

在那里，我有一个code，它通过背包算法计算的最优值（装箱NP问题）：

There I have a code, which calculates the optimal value by 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];
}

此外，我需要的元素，包括包装，以显示。我想创建一个数组，将有一个额外的元素。所以，问题是在哪一步把这个除此之外，或者是有没有其他更有效的方法来做到这一点？

Also I need the elements, included to pack, to be shown. I want to create an array, to put there an added elements. So the question is in which step to put this addition, or maybe is there any other more efficient way to do it?

问：我希望能够知道给我最佳的解决方案中的项目，以及最佳的解决方案，而不仅仅是值

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

PS。对不起，我的英语，这不是我的母语。

PS. Sorry for my English, it's not my native language.

推荐答案

让你从包可以做矩阵使用数据形成矩阵，并且不保存任何额外的数据元素。
伪code：

getting the elements you pack from the matrix can be done using the data form the matrix, without storing any additional data.
pseudo code:

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: 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.

这篇关于如何找到哪些元素是囊中，用背包算法[不仅包的价值]的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！