We have seen the problem of a thief in the earlier posts, Fractional Knapsack problem. If you haven’t, check it out now. From the fractional Knapsack problem, we are aware that things can be partitioned and taken according to the profit. But from the heading itself one can understand that in the 0/1 Knapsack problem, we cannot divide things. Then how we can achieve our solution. Let’s dive into the details.

Suppose the sets of profit and weight are respectively as follows: P={1,2,5,6} and W= {2,3,4,5}. Let us tabulate our procedure and understand along the way. Here the number of objects are 4 and the capacity of the knapsack is 8. n=4; wt=8

Legend:

Say, the name of the Table is V and V[i,w] used to represent the elements in the table. For example, V[1,2] = 1. Here, i indicates the row and w indicates the column.

The weight increases following w horizontally →.

P_i and w_i are the corresponding profits and weights of the objects.

“i” is for the number of objects along the rows. If i=3, it shows that it is object 3.

We shall fill the profits in the cells with respect to weights w. It will be clear when solving.

Procedure to solve:

The initial row is set to zero as we haven’t filled anything into the sack. The count starts when i=1.

In the first row (i=1), the weight of the object is 2, and the profit is 1. So, we fill “1” i.e. profit, where weight is 2 (w=2) in the table (V[1,2]). Since we don’t have any objects earlier to put into the sack, we fill all 1s (profit of current object) in the remaining cells of the table.

In the second row (i=2), the weight of the object is 3, and the profit is 2. So, we fill “2” i.e. profit, where weight is 3 (w=3) in the table (V[2,3]. The earlier values remain the same for w=0, 1, and 2. Now, we have an object in the sack already i.e. i=1. We have to now fill the combined weight of the two i.e. 3+2 = 5. The profit for the combination is 3. So, we fill the profit in the column where w=5 (since the combined weight is 5) (V[2,5]). What about the remaining columns? Since the maximum profit achieved is 3 for a weight of 5, obviously for w=6, 7, and 8 also we will have a profit of 3 only. Why because we don’t have any other objects to put in our sack till now.

Things will get a little complicated. Notice carefully.

In the third row (i=3), the weight of the object is 4 and the profit is 5. So, we fill “5” where w=4 in the table (V[3,4]). Now, how many objects do we have in our sack earlier? Two. Let’s look at the possibilities. 

We have a weight of 4 at i=3. The profit is 5. There can be combinations of objects now.

If we take all three objects (i=1, 2, and 3), the overall weight would be 9 and the profit is 8. Do we have a capacity of 9 in our Knapsack? No, the maximum capacity of our knapsack is 8. What do we do now?

The combination of i=1 and i=3 yields a profit of 6 and weight sums up to 6. Fill the profit in the table where w=6 i.e. V[3,6]. Why in this row? Because we are taking with the combination of the third object (i=3).

The combination of i=2 and i=3 yields a profit of 7 and weight sums up to 7. Fill the profit in the table where w=7 i.e. V[3,7]

What is the maximum profit we achieved till now? 7 for a weight of 7. So, for a weight of 8 also the profit remains the same i.e. 7. Hence, V[3,8]=7.

For the fourth row, i=4:

w=5 and the profit P=6. So, V[4,5]=6.

For combinations of:

i= 4, 3, 2, and 1; w=14 →not acceptable.

i=4,3 and 2; w=12 →not acceptable.

If the process continues, the only combinations which are valid come out to be:

i=4 and 1; w=7 and the profit is 7. So, V[4,7]=7

i=4 and 2; w=8 and the profit is 8. So, V[4,8]=8.

All the other values remain the same.

The values in the table can also be filled using the formula:

V[i,w]=maximum{V[i-1,w], V[i-1,w-w[i] + P[i]}

P→Profit; w[i]→w(subscript i)
If the location is invalid, ignore the value and 
fill the earlier values to the cells.
Ex:
V[4,1](i=4,j=1)=max{V[3,1],V[3,1-5]+6}
=max{0,V[3,-4](location not valid)+6}
So, fill V[4,1] with earlier value i.e. 0
Same goes with the remaining.

The maximum profit we have is 8. Now, which objects have to be included in the knapsack to achieve the maximum profit?

Starting from the last object, we have a profit of 6 from object 4. We can include object 4 and subtract the profit of object 4 from the maximum profit. So, 8-6 = 2 is the profit remained. We have to now check by including which object we can get a profit of 2.

Check for 2 in the above row (i=3). Is there a 2? Yes, it is. But is it solely achieved from object 3? No. Why because there is one more 2 in the above row as well (i=2). It can be understood that it is obtained by including another object, not 2. Now check in the above row for 2. Yes, it exists. It is achieved from object 2. Hence, include object 2. The remaining profit is 2-2=0. So, we got our solution.

Including objects 2 and 4 gives a maximum of profit 8. We can simply tell from the set of objects given. But if that is the case, we have to calculate combinations of 2⁴ = 16. For larger sets, the number would exponentially increase. So, to decrease the complexity of the problem, we used dynamic programming here.

We have obtained all the possible solutions (brute force) indirectly and selected the required solution. Hope the things are clear for now. Various methods of implementing the 0/1 Knapsack problem will be up soon. For queries and suggestions, comment below!

References and Recommendations:

• Dynamic Programming
• Fractional Knapsack Problem
• Prim’s Algorithm
• Time complexity
• Greedy Method