Alex Rivera | Logout

How to find which elements are in the bag, using Knapsack Algorithm [and not only the bag's value]?

Asked 2011-09-20T17:43:29.577
19

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.

Edit
Report

1 Answer

2
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
    cw = cw - weight(i)
    i <- i-1
  else if dp[line][i] > dp[line][i-1]:
    line <- line - 1
  else: 
    i <- i-1

Just remember how you got to dp[line][i] when you added item i

dp[line][i] = dp[line - weight(i) ][i - 1] + value(i);
answered 2012-07-30T22:29:31.150

Your Answer