- #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: