- #1
zak100
- 462
- 11
- Homework Statement
- Can't understand knapsack problem for Dynamic Programming
- Relevant Equations
- Table[i][j] := max(w + Table[i][j-w], Table[i-1][j])
Hi,
I am working on the following example provided at:https://riptutorial.com/dynamic-programming/example/25787/0-1-knapsack-problem
+----------+---+---+---+---+
| Item | 1 | 2 | 3 | 4 |
+----------+---+---+---+---+
| Weight | 1 | 3 | 4 | 5 |
+----------+---+---+---+---+
| Value | 1 | 4 | 5 | 7 |
+----------+---+---+---+---+
At this link:
I found that n represents the number of items and w represents weight units. There should be n+1 rows and w+1 columns as discussed in the above link.
In the example we w = 7 and n= 4, therefore there should be 5 rows and 8 columns. There are 8 columns but only 4 rows. I can’t understand why they have used n= 4 rows in the example at:
https://riptutorial.com/dynamic-programming/example/25787/0-1-knapsack-problem
Then they started filling the first column: Table[0][0], Table[1][0], Table[2][0], Table[3][0]. This will all be zeros, this is because capacity is zero in all the above cases.
But for first row, I am confused:
Table[0][0]: capacity is 0, so its 0 (OK)
Table [0][1]: capacity is 1, so its 1 (OK)
Table[0][2]: capacity is 2, but no item with weight 2, so 1 is fine
Table[0][3]: capacity is 3, we have an item of weight 3 so we can write 3, but they wrote 1, I can’t understand
Some body please guide me why:
n=4?
and why Table[0][3], Table[0][4]...Table[0][7] == 1?
Zulfi.
I am working on the following example provided at:https://riptutorial.com/dynamic-programming/example/25787/0-1-knapsack-problem
+----------+---+---+---+---+
| Item | 1 | 2 | 3 | 4 |
+----------+---+---+---+---+
| Weight | 1 | 3 | 4 | 5 |
+----------+---+---+---+---+
| Value | 1 | 4 | 5 | 7 |
+----------+---+---+---+---+
At this link:
I found that n represents the number of items and w represents weight units. There should be n+1 rows and w+1 columns as discussed in the above link.
In the example we w = 7 and n= 4, therefore there should be 5 rows and 8 columns. There are 8 columns but only 4 rows. I can’t understand why they have used n= 4 rows in the example at:
https://riptutorial.com/dynamic-programming/example/25787/0-1-knapsack-problem
Then they started filling the first column: Table[0][0], Table[1][0], Table[2][0], Table[3][0]. This will all be zeros, this is because capacity is zero in all the above cases.
But for first row, I am confused:
Table[0][0]: capacity is 0, so its 0 (OK)
Table [0][1]: capacity is 1, so its 1 (OK)
Table[0][2]: capacity is 2, but no item with weight 2, so 1 is fine
Table[0][3]: capacity is 3, we have an item of weight 3 so we can write 3, but they wrote 1, I can’t understand
Some body please guide me why:
n=4?
and why Table[0][3], Table[0][4]...Table[0][7] == 1?
Zulfi.
Last edited by a moderator: