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.
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.
