Comp Sci Solving 0-1 Knapsack Problem: Understanding n, w and Table[0][3]

[zak100]

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.

 

[pbuk]

In row[0] you only consider item[0] item[1] (it would be much easier if they used the same index basis) so no entry in row[0] can have a value greater than the value of item[1] = 1. In row[1] you start to consider item[2] and as this has weight 3 and value 4 you write 4 in table[1][3].

 

[zak100]

Hi,

I think you are right. They have used different index for instance weight[2] means 2nd element even though they are starting from zero.
Please guide me this:

Among the two choices, we'll pick the one from which we can get maximum value. If we select the item, we get: value for this item + maximum value from rest of the items after taking this item = 4 + 0 = 4.

What are the two choices they are talking about? Which item are they talking about when they are saying:

value for this item

.

Please explain me the quote before the previous one.

Zulfi.

 

[pbuk]

What are the two choices they are talking about? Which item are they talking about when they are saying:

value for this item

The two choices are in the text immediately before that:

Now for Table[1][3] since our maximum capacity is equal to our current weight, we have two choices.

• We pick the item and add its value with the maximum value we can get from other remaining items after taking this item.
• We can exclude this item.

but I agree it's not very clear. I am not sure about clarifying text from some ad-carrying site which seems to have ripped off content from StackExchange, but I will give this one more go by writing that whole section more clearly.

Now for Table[1][3] since our maximum capacity of 3 (given by the column index) is equal to the weight of the current item (item 2, given by the row index offset by 1 because we didn't zero base our items), for the first time we can decide whether to include the item or not.

1. if we do not include the item we carry forward the value of 1 from Table[1][2]
2. if we include item 2 we can take its value of 4. Because we are in column 3 with weight 3 we know we can't take any more items, but in general we do not know that and so I am going to explain the computation because this is critical to understanding the elegance of the algorithm and why we have bothered to set up the table this way:
   For an item with weight w in Table[r][c] we look up the value in Table[r-1][c-w]; this is the optimum solution for the remaining capacity of (total capacity - w).
3. In this case, Table[r - 1][c - w] = Table[1 - 1][3 - 3] = Table[0][0] = 0 so if we take item 2 we get a total value of 4 + 0 = 4. 4 is better than 1 (from step 1 above) so we take 4.

 

[zak100]

Hi,
<

1. For an item with weight w in Table[r][c] we look up the value in Table[r-1][c-w]; this is the optimum solution for the remaining capacity of (total capacity - w).
2. In this case, Table[r - 1][c - w] = Table[1 - 1][3 - 3] = Table[0][0] = 0 so if we take item 2 we get a total value of 4 + 0 = 4. 4 is better than 1 (from step 1 above) so we take 4.

>
Thanks for explaining me this critical step. I was actually having wrong assumption that we have to add weight in the table. This means that table is taking care of value. I have two questions:

i)Why are we not keeping track of total weight of items stored in the knapsack and the value by using separate variables? This is confusing that same array is tab=king care of both weight and value.
ii) Why are we adding weight with value :w + Table[i-1][j-w] as you have said that:

weight is stored in Table[r][c] and value in Table[r-1][c-1]
Thanks for your cooperation.

Zulfi.

 

[pbuk]

i)Why are we not keeping track of total weight of items stored in the knapsack and the value by using separate variables?

Because we don't need to keep track of the total weight anywhere.

This is confusing that same array is taking care of both weight and value.

It isn't. The columns represent capacity, the rows represent items and the cells represent value. As above, we don't need to keep track of the total weight of items because that is not how the algorithm works.

ii) Why are we adding weight with value :w + Table[i-1][j-w] as you have said that:

weight is stored in Table[r][c] and value in Table[r-1][c-1]

We aren't, and I didn't say that. Is this clearer:

To work out the value to store in Table[r][c] we take the weight w of the item under consideration in the current row (which ought to be Weights[r] but because they chose not to zero base the items it is Weights[r+1] here) and we look up the value in Table[r-1][c-w]. This is the value of the optimum solution for the remaining capacity of (total capacity - w) which is the capacity we would have left if we include the current item.

 

[zak100]

Hi,

Thanks. I am trying to write what you wrote in post#4:

Table[1] means row 1. The row index deals with weight. So weight[1] means weight = 3. The column index is 4. Column index deals with capacity. So weight is 3 and capacity is 4 so its OK.Now value of weight 3 is 4. So we would decide whether we want to carry the weight or not. For this we would calculate: Table[r-1][[c-w] = Table[1-1][4-3] = Table[0][1]=1. So if we take item 2, we get a total value of 4+1 = 5 which is better than ?

What you mean by:

(from step 1 above)

Somebody please guide me.

Zulfi.

 

[pbuk]

You are nearly there, [comments below]:

Table[1] means row 1 [yes]. The row index deals with weight [no, the row index deals with items, so it determines both the weight and the value of the current item]. So weight[1] means weight = 3 [almost - because of the stupid idea of the article you posted to zero base rows but not items so for weight[row[1]] = weight[2] = 3]. The column index is 4. Column index deals with capacity [yes]. So weight is 3 and capacity is 4 so its OK [yes, but we don't need to check this at this stage - see *]. Now value of weight 3 is 4. So we would decide whether we want to carry the weight or not. For this we would calculate: Table[r-1][[c-w] = Table[1-1][4-3] = Table[0][1]=1 [yes: * if c - w < 0 we know we can't take the item so we skip this step]. So if we take item 2, we get a total value of 4+1 = 5 [yes] which is better than [the value from Table[r][c-1] which is the optimum value of a knapsack with 1 unit less capacity]

As I have said before in this thread, this last point is at the crux of the algorithm - it is nothing to do with dynamic programming[1], it is simply the forward calculation of a recursive relationship: presented with a backpack with a capacity of c and an item of value v and weight w, the optimum solution is either the same as the optimum solution for a backpack with capacity of c - 1, or the same as a backpack with capacity c - w plus v.

If you still don't understand, keep re-reading that sentence above, it is not worth spending any more time improving on someone else's poor explanation.

[1] Edit - I was wrong to say this has nothing to do with dynamic programming so have struck out this statement.