How to find which elements are in the bag, using Knapsack Algorithm [and not only the bag's value]?
Solution 1:
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.
Solution 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);
Solution 3:
The algorithm for reconstructing items taken in bounded 0/1 knapsack is simpler than some of the existing code in this thread may lead one to believe. This answer aims to demystify the procedure a bit and provide a clean, direct implementation alongside a worked example.
The approach
Begin with two indices respective to the table axes: a weight variable initialized to the knapsack capacity and an index i that loops backwards over the DP lookup table along the item axis, stopping at index 1 (the algorithm uses i-1 so stopping at 1 avoids an out of bounds access).
In the loop, if T[weight][i] != T[weight][i-1], mark item i-1 as selected, deduct its weight and continue stepping backwards along the item axis.
Time complexity of the reconstruction is O(length(items)).
Here is Python as pseudocode:
def reconstruct_taken_items(T, items, capacity):
taken = []
weight = capacity
for i in range(len(items), 0, -1): # from n downto 1 (inclusive)
if T[weight][i] != T[weight][i-1]:
taken.append(items[i-1])
weight -= items[i-1].weight
return taken
Example
For example, consider a knapsack capacity of 9 and these items:
[item(weight=1, value=2),
item(weight=3, value=5),
item(weight=4, value=8),
item(weight=6, value=4)]
The best value is 15 by taking items 0, 1 and 2.
The DP lookup table is
items ---->
0 1 2 3 4
--------------+
0 0 0 0 0 | 0 capacity
0 2 2 2 2 | 1 |
0 2 2 2 2 | 2 |
0 2 5 5 5 | 3 v
0 2 7 8 8 | 4
0 2 7 10 10 | 5
0 2 7 10 10 | 6
0 2 7 13 13 | 7
0 2 7 15 15 | 8
0 2 7 15 15 | 9
Run the reconstruction algorithm on this:
0 0 0 0 0
0 2 2 2 2
0 2 2 2 2
0 2 5 5 5
0 2 7 8 8
0 2 7 10 10
0 2 7 10 10
0 2 7 13 13
0 2 7 15 15
0 2 7 15 15 <-- weight = capacity = 9
^ ^
| |
i-1 i = length(items) = 4
In the initial state above, T[weight][i] == T[weight][i-1] (15 == 15) so item[i-1] (item(weight=6, value=4)) wasn't taken. Decrement i and try the remaining items with the same capacity.
0 0 0 0 0
0 2 2 2 2
0 2 2 2 2
0 2 5 5 5
0 2 7 8 8
0 2 7 10 10
0 2 7 10 10
0 2 7 13 13
0 2 7 15 15
0 2 7 15 15 <-- weight = 9
^
|
i = 3
Here, T[weight][i] != T[weight][i-1] (7 != 15) so items[i-1], which is items[2], or item(weight=4, value=8), must have been taken. Decrement the weight remaining by items[i-1].weight, or 9 - 4 = 5, and try the remaining items with the smaller weight left over after taking item[i-1] out of the picture.
0 0 0 0 0
0 2 2 2 2
0 2 2 2 2
0 2 5 5 5
0 2 7 8 8
0 2 7 10 10 <-- weight = 5
0 2 7 10 10
0 2 7 13 13
0 2 7 15 15
0 2 7 15 15
^
|
i = 2
In this state, we again have T[weight][i] != T[weight][i-1] (2 != 7) so we must have taken items[i-1], which is items[1], or item(weight=3, value=5). Decrement the weight remaining by items[i-1].weight, or 5 - 3, and move to the next item.
0 0 0 0 0
0 2 2 2 2
0 2 2 2 2 <-- weight = 2
0 2 5 5 5
0 2 7 8 8
0 2 7 10 10
0 2 7 10 10
0 2 7 13 13
0 2 7 15 15
0 2 7 15 15
^
|
i = 1
In this last step, we again have T[weight][i] != T[weight][i-1] (0 != 2) so we must have taken items[i-1], which is items[0], or item(weight=1, value=2). Decrement the weight remaining by items[i-1].weight, or 2 - 1, and exit the loop because i == 0.
C++ implementation
#include <iostream>
#include <vector>
class Knapsack {
public:
struct Item {
const int weight;
const int value;
};
private:
static std::vector<Item> reconstruct_taken_items(
const std::vector<std::vector<int> > &T,
const std::vector<Item> &items,
const int capacity
) {
std::vector<Item> taken;
int weight = capacity;
for (size_t i = items.size(); i > 0; i--) {
if (T[weight][i] != T[weight][i-1]) {
taken.emplace_back(items[i-1]);
weight -= items[i-1].weight;
}
}
return taken;
}
public:
static std::vector<Item> solve(
const std::vector<Item> &items,
const int capacity
) {
std::vector<std::vector<int> > T(
capacity + 1,
std::vector<int>(items.size() + 1, 0)
);
for (int i = 1; i <= capacity; i++) {
for (size_t j = 1; j <= items.size(); j++) {
const Item &item = items[j-1];
if (item.weight > i) {
T[i][j] = T[i][j-1];
}
else {
T[i][j] = std::max(
T[i-item.weight][j-1] + item.value,
T[i][j-1]
);
}
}
}
return reconstruct_taken_items(T, items, capacity);
}
};
int main() {
const int capacity = 9;
const std::vector<Knapsack::Item> items = {
{1, 2}, {3, 5}, {4, 8}, {6, 4}
};
for (const Knapsack::Item &item : Knapsack::solve(items, capacity)) {
std::cout << "weight: " << item.weight
<< ", value: " << item.value << "\n";
}
return 0;
}
See also
- Printing Items that are in sack in knapsack
- Knapsack 0-1 path reconstruction (which items to take)