# KnapSack Problem: Can't understand the working

#### zulfi100

Joined Jun 7, 2012
656
Hi,
This is not my work but I am of course studying this topic. I don't know where to post it but I am posting on this forum because I was told to post course stuff on HW help.

KnapSack Example

+----------+---+---+---+---+

| Item | 1 | 2 | 3 | 4 |

+----------+---+---+---+---+

| Weight | 1 | 3 | 4 | 5 |

+----------+---+---+---+---+

| Value | 1 | 4 | 5 | 7 |

+----------+---+---+---+---+

At the following link, I found:

Another Example

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

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 4 rows?

Then the started filling the first column: Table, Table, Table, Table. This will all be zeros, this is because capacity is zero in all the above cases.

But for first row, I am confused:

Table: capacity is 0, so its 0 (OK)

Table : capacity is 1, so its 1 (OK)

Table: capacity is 2, but no item with weight 2, so 1 is fine

Table: capacity is 3, we have an item of weight 3 so we can write 3, but they wrote 1, I cn’t understand