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

• Comp Sci
• zak100
In summary: Weights[r-1]) and add it to the maximum value from the remaining capacity c - w. We get this maximum value from the cell in the previous row (r-1, which ought to be r) and column c - w.
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 |

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

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

zak100 said:
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.

jim mcnamara and 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.

zak100 said:
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.

zak100 said:
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.

zak100 said:
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.

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.

You are nearly there, [comments below]:
zak100 said:
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.

Last edited:

1. What is the 0-1 Knapsack Problem?

The 0-1 Knapsack Problem is a classic optimization problem in computer science where a set of items with different weights and values must be packed into a knapsack with a maximum weight capacity. The goal is to maximize the value of the items in the knapsack without exceeding its weight limit.

2. What is the significance of n and w in the 0-1 Knapsack Problem?

In the 0-1 Knapsack Problem, n represents the number of items available and w represents the maximum weight capacity of the knapsack. These two variables are important in determining the size and constraints of the problem, and are used in the algorithm for solving it.

3. What is the purpose of the Table[0][3] in the 0-1 Knapsack Problem?

The Table[0][3] is a two-dimensional array used in the dynamic programming approach to solve the 0-1 Knapsack Problem. It stores the maximum value that can be achieved for a given weight and number of items. This table is crucial in finding the optimal solution to the problem.

4. How does the dynamic programming approach solve the 0-1 Knapsack Problem?

The dynamic programming approach for solving the 0-1 Knapsack Problem involves breaking down the problem into smaller subproblems and storing their solutions in a table. By using this table, the algorithm can efficiently calculate the maximum value that can be achieved for any given weight and number of items, ultimately leading to the optimal solution.

5. What are some real-world applications of the 0-1 Knapsack Problem?

The 0-1 Knapsack Problem has many practical applications, such as in resource allocation, financial portfolio optimization, and project scheduling. It is also commonly used in the fields of operations research, logistics, and computer science for various optimization problems.

• Engineering and Comp Sci Homework Help
Replies
1
Views
1K
• Engineering and Comp Sci Homework Help
Replies
3
Views
1K
• Engineering and Comp Sci Homework Help
Replies
4
Views
1K
• Linear and Abstract Algebra
Replies
2
Views
865
• Nuclear Engineering
Replies
7
Views
2K
• Engineering and Comp Sci Homework Help
Replies
2
Views
2K
• Nuclear Engineering
Replies
7
Views
1K
• Engineering and Comp Sci Homework Help
Replies
21
Views
2K
• Precalculus Mathematics Homework Help
Replies
21
Views
1K
• Classical Physics
Replies
2
Views
1K