KnowledgeHub
Questions
Tags
Users
Search
Alex Rivera
|
Logout
Edit Question
Title
Body
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.
Tags (comma-separated)
Save Edits
Cancel