DP #02. 0 1 Knapsack problem - mbhushan/dynpro GitHub Wiki
(2). 0/1 Knapsack problem
Given a bag with weight W and a list of items having a certain
weight and value, how would you fill the bag so that you have
maximum value?
Another variation of this problem is unbounded knapsack problem
where an item can be repeated which is much simpler in the sense
just take the value/weight ratio for each item then sort them in
decreasing order and keep adding the item until you have no
capacity left.
| (Weight, Value) |
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
| (1, 1) |
0 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
| (3, 4) |
0 |
1 |
1 |
4 |
5 |
5 |
5 |
5 |
| (4, 5) |
0 |
1 |
1 |
4 |
5 |
6 |
6 |
9 |
| (5, 7) |
0 |
1 |
1 |
4 |
5 |
7 |
8 |
9 |
Formula:
i denotes row and j column.
Row would be the list of items. wt(i),val(i)
Col would be weights from 0 to W (capacity of the bag).
If (wt[i] > j) {
T[i][j] = T[i-1][j]
} else {
T[i][j] = Max(
T[i-1][j - wt[i]] + val[i],
T[i-1][j]
);
}
- Time complexity - O(W*total items)
Knapsack - 0/1