Cant understand knapsack problem

[zak100]

Hi,

I am trying to understand knapsack problem from the following site:

 

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 |

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

 

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:

https://medium.com/@fabianterh/how-to-solve-the-knapsack-problem-with-dynamic-programming-eb88c706d3cf

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

[Ghideon]

Hello.

It is a little tricky to see which numbers you picked from which source.

8 hours ago, zak100 said:

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:

https://medium.com/@fabianterh/how-to-solve-the-knapsack-problem-with-dynamic-

-eb88c706d3cf

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

The example at medium.com has 5 rows so the question regarding 4 rows I guess is related to your first link (riptutorial). The first tutorial probably just skipped the trivial first row, since there are no massless and zero-value items to consider.

 

8 hours ago, zak100 said:

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

First row only contains the first item so first row has item no 1 in all the knapsacks that have capacity to store that item. Generally a row number i represents the set of all the items from rows 1— i. The example at medium says the following for row 3:

Quote

For instance, the values in row 3 assumes that we only have items 1, 2, and 3.

From your link https://medium.com/@fabianterh/how-to-solve-the-knapsack-problem-with-dynamic-programming-eb88c706d3cf

So in your case the example has weight 3 for item no 2 and therefore will not be used on line 1: 

|Weight | 1 | 3 | 4 | 5 |

Hence the item with weight 3 is considered on lines >= 2 (lines 2,3,...)

 

[zak100]

Hi,

Thanks for your response.

Okay lets start with row2 which is Table[1][*]. I am just concentrating on riptutorial

Quote

Moving on, for Table[1][1], we are asking ourselves, if we had item 1 and 2 and if the maximum capacity of our knapsack was 1, what is the maximum value we can get? If we take both item 1 and 2, the total weight will be 4, which will exceed our current knapsack capacity. So item 2 can't be selected.

 Okay I understand this. But still I would add on for future reference: Table [1][1] = 2nd row. item 1 above means weight '1' item and item 2 means weight '3' item. Total weight for both item 1 & item 2 = 3 +1 =4 correct (as above) and exceeds the knapsack capacity because capacity was 1 in case of Table[1][1].

 

Quote

For Table[1][2], since 2 is less than weight[2], that is the weight of the second item, we can't take the item. So we can establish that, if the weight of the current item is greater than our maximum capacity, we can't take that item. In this case, we'll simply take the value from top, which represents the maximum value we can take excluding the item.

For Table[1][2], capacity =2. weight[2], if we are starting from 0 it should be weight[1] but they later clarified it that they mean second item. weight of current item = weight of 2nd item i.e. 3. At this point for Table[1][2] maximum capacity is 2 and current item i.e. the item with weight 3 is greater than the capacity 2. value from top =1 , correct, so they filled 1 in the table[1][2] which is correct. Now we would go ahead.

 

Quote

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

capacity is 3 and current weight is 3, so they are correct.

Quote

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 2 choices they are talking about?

Quote

if we select the item, we get:

Which item are they talking about?

 

Can you please explain me the rest of the stuff also i.e.

Quote

value for this item + maximum value from rest of the items after taking this item = 4 + 0 = 4. 

 Please guide me.

 

Thanks for your cooperation.

 

Zulfi.

[Ghideon]

18 hours ago, zak100 said:

Please guide me.

Advice: Wouldn't it be better to try to understand how the algorithm works rather than to try to untangle some specific example out of the many available on the net?

 

18 hours ago, zak100 said:

Which item are they talking about?

The second item, the item having value 4.

 

18 hours ago, zak100 said:

What are the 2 choices they are talking about?

They are likely talking about the two choices available in the algorithm at that point: Including the item i or not including the item i.
Basically the algorithm tests if the total value of the knapsack gets higher if we add item i and remove other items as needed to make item i fit in the knapsack. That is the central part of the algorithm. Have you yet understood how that works? If not, the tutorial(s) and examples will be hard to understand.

To allow for the discussion to take place here, without having to follow links, the two choices (selecting or not selecting an item i) can be stated* as:

if weight[i] > j //too heavy
    Table[i][j] := Table[i-1][j]
else // can be carried
	w := weight[i]
	v := value[i]
    Table[i][j] := max(v + Table[i][j-w], Table[i-1][j]) 
end if

Where i is the item, 1<= i <= number of items

j is the capacity of (current, dynamic) knapsack, 1<= j <= max capacity of knapsack

weight[] and value[] holds weights and values of the items

 table[][] holds the calculated values of the knapsacks

 

To allow for other members to take part easier, here is a description of Knapsack 0-1 problem: 
-We have a Knapsack that has a weight capacity C.
-We want to maximise the value so that the total weight of items in the knapsack is at most C where C is an integer.
-0-1 Knapsack problem means we are allowed to either take an entire item or reject it completely. We can not break an item and put parts in the knapsack.
-Available items are i1, i2, ..., in.  Each item having weight w1, w2, … wn and some value v1, v2, ... vn

Also see: https://en.wikipedia.org/wiki/Knapsack_problem#0-1_knapsack_problem

 

 

*) Disclaimer; I haven't visited these algorithms for some time, room for errors
 

 

Edited February 27, 2020 by Ghideon
format and grammar, some clarifications

[zak100]

Hi,

Thanks for your reply.

<Advice: Wouldn't it be better to try to understand how the algorithm works rather than to try to untangle some specific example out of the many available on the net?>

 

Actually I chose this example because I saw the attached graph.

The following is very useful:

 

Quote

 

To allow for the discussion to take place here, without having to follow links, the two choices (selecting or not selecting an item i) can be stated* as:

if weight[i] > j //too heavy
    Table[i][j] := Table[i-1][j]
else // can be carried
	w := weight[i]
	v := value[i]
    Table[i][j] := max(v + Table[i][j-w], Table[i-1][j]) 
end if

Where i is the item, 1<= i <= number of items

j is the capacity of (current, dynamic) knapsack, 1<= j <= max capacity of knapsack

weight[] and value[] holds weights and values of the items

 table[][] holds the calculated values of the knapsacks

 

When you are saying  "can be carried" why are we not increasing the value and weight of knapsack. I mean in the else part, do we not need variables to hold the collective values of weight and values. Where are variables representing the total weight and value of knapsack?

 

Kindly guide me.

Zulfi.

[Ghideon]

15 hours ago, zak100 said:

Actually I chose this example because I saw the attached graph.

Ok! 

15 hours ago, zak100 said:

When you are saying  "can be carried" why are we not increasing the value and weight of knapsack.

Because

Table[i][j] 

Holds the maximum value for a knapsack of capacity j when considering the first i items (out of the total n items). That is one central part of the algorithm*. That means that 

Table[n][C]

Holds the maximum value, the solution to the problem. n=number of items and C=capacity of knapsack

15 hours ago, zak100 said:

I mean in the else part, do we not need variables to hold the collective values of weight and values. Where are variables representing the total weight and value of knapsack?

That is part of the Dynamic Programming approach, not needing the additional storage. Of course one can use variables to hold the values (that is more of an implementation question) but it is not needed to get the solution. 

Once the table is filled the list of items that gives the maximum value of the knapsack can be retrieved by examining the table "backwards" from last line. Start on last line (i=n) and max capacity (j=C) repeat:

if Table[i,j] != V[i-1,j] then // item i is in knapsack
    //mark the ith item or add to some list (code not shown)    
    j := j - weight[i] //remove item i from knapsack capacity
    i := i - 1 //move to previous line
else // item i is not in knapsack
    i := i - 1
end if
  

Note that the this last iteration through the table only visit one element at each line making it rather efficient. 

 

*) Note that this a property of the knapsack 0-1; the fact that the problem can be optimally solved by looking at one item at a time and increasing knapsack capacity. It would be off topic to dig into the details of the properties of problems where dynamic programming applies (https://en.wikipedia.org/wiki/Dynamic_programming) and how the class of problems differs from others.