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