KnapSack Problem: Can't understand the working

Thread Starter

zulfi100

Joined Jun 7, 2012
632
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.

I am reading about KnapSack problem from the following link1:
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:



In the example at link1:


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[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 cn’t understand

Some body please guide me.

Zulfi.
 
Top