Knapsack algorithm with Step by Step explanation and example
Vikram Chaudhary
In this article I will discuss about one of the important algorithm of the computer programming. This is known as knapsack algorithm. This is called the by this particular name as we have to solve here a problem with in which we are provided with some specific items with their weights and values and a knapsack with some capacity.
The knapsack algorithm can be used to solve a number of programming problems asked by top product based companies in interview. The companies like Google, Facebook, Amazon will have some interview question based on this algorithm.
We should place all those items in the knapsack in such a way that they the all the items weight should not exceed the knapsack’s capacity and still having maximum value. Each item can be placed zero or one time.
This algorithm is a part of the dynamic programming. In dynamic programming we solve the bigger problem by diving it into smaller problems. Keep the result of the smaller problems in cache and then solving the bigger problem using the cache.
In the above figure I have listed all the items with their weights and values. Finally I want to put these inside the knapsack. Though the number of the items are smaller we can solve this problem easily. But suppose we have a huge number of the items to be arranged. In that scenario we need some particular algorithm to solve this problem.
Can we try to solve the above problem using brute force algorithm where we just include each item 0 or 1 time.
For three items we will have : 2*2*2 = (2) to the power of 3 combinations and for n items we will have (2) to the power of N items. This will result in explosion of result and in turn will result in explosion of the solutions taking huge time to solve the problem.
The Knapsack Algorithm Solution
To solve this problem we need to keep the below points in mind:
Divide the problem with having a smaller knapsack with smaller problems. We can start with knapsack of 0,1,2,3,4 capacity.
M[items+1][capacity+1] is the two dimensional array which will store the value for each of the maximum possible value for each sub problem. The row and column contains one items extra considering the solution with zero capacity and no item.
M[i][capacity] = max(E, I)
where
E(If excluded) = M[i-1][capacity] and
I(If included and small enough) = value(i) + M[i-1][capacity – weight]
Lets have a look at the array which we have to create.
The rows are the items with their weights and value respectively. The columns are the capacity starting from zero to the maximum value. Now I will fill all the array items one by one and lets see the result.
M[1][1] : I have taken a case where we suppose the capacity of the knapsack is 1 unit and we have only one item available i.e Eraser. The weight of the eraser i.e. 2 unit is more than capacity of the knapsack. We cannot include the eraser we assign zero to this array item. M[1][1] = 0
M[1][2] : Now for the next array item. The capacity of the knapsack is increased to 2 unit, but we will continue with Eraser only as the items present. The weight of the eraser i.e 2 unit is equal to the capacity of the knapsack i.e 2 unit. Here we have to consider both the cases.
if excluded E(If excluded) = M[i-1][capacity] = 0
If included and small enough I = value(i) + M[i-1][capacity – weight] = 3 + 0 = 3
Max(E,I) = Max(0,3) = 3
therefore M[1][2] = 3
The next two array items i.e M[1][3] and M[1][4] have the capacity of the knapsack as 3 and 4, but there are no other item. In both of these case Eraser will be included with 3 as the value.
M[1][3] = 3
M[1][4] = 3.
After the above iteration for the above row, our array should look as shown in the below figure.
Now coming to the next row.
Now we will build the sub solution for the two items. And we will use the cached solution which we have already built using the first item. The two items which we will use in this solution will be Eraser and Pencil each having weight 2 and value as 3 and 1 respectively.
M[2][0] = Since the pencil has a weight of 2 which is greater then the weight for the sub solution which is 1. We simply cannot include Pencil in this sub solution.
Therefore from the above formula for excluded object m[i-1][Capacity] = 0.
For M[2][1]
If Excluded(E) : m[i-1][Capacity] = 3
If Included & Small Enough(I): value(i) + M[i- 1][capacity – weight] = 1 + 0 = 1
M[i][Capacity] = max(E, I) = max (3, 1) = 3
I hope the above formula is self explanatory. If we exclude this item. We can get the value from the cache.
If we include the item, the value of the item is 1 and if the weight is less than capacity we get the remaining value from cache.
And we need to select the maximum of these two. The value for this array will be 3 and not selected.
M[2][2]
The calculation will be same as previous cell.
And we get the value as 3 which is not selected.
M[2][3]
If Excluded(E) : m[i-1][Capacity] = 3
If Included & Small Enough(I): value(i) + M[i- 1][capacity – weight] = 1 + 3 = 4
M[i][Capacity] = max(E, I) = max(3, 4) = 4
After the iteration for the second row our array looks like below.
Now coming to the last item of the array. In this case we will consider all the three items. And we will build the solution based on the already cache present for previous two items.
M[3][0]:
If Excluded(E) : m[i-1][Capacity] = 0
If Included & Small Enough(I): value(i) + M[i- 1][capacity – weight] = 3 + 0 = 3
M[i][Capacity] = max(E, I) = max(0, 3) = 3
M[3][1]
If Excluded(E) : m[i-1][Capacity] = 3
If Included & Small Enough(I): value(i) + M[i- 1][capacity – weight] = 3 + 0
M[i][Capacity] = max(E, I) = 3, 3 = 3
M[3][2]
If Excluded(E) : m[i-1][Capacity] = 3
If Included & Small Enough(I): value(i) + M[i- 1][capacity – weight] = 3 + 3 = 6
M[i][Capacity] = max(E, I) = max(3, 6) = 6
M[3][3]
If Excluded(E) : m[i-1][Capacity] = 4
If Included & Small Enough(I): value(i) + M[i- 1][capacity – weight] = 3 + 3 = 6
M[i][Capacity] = max(E, I) = max(4,6) = 6
And finally our array should like as shown below:
Selection of Items for Knapsack
We need to select the items which we have to consider for the knapsack.
We need to exclude the items which we cannot take for the knapsack. After excluding the items, our array should like below.
By iterating though the array we got that the maximum value of the items we can store is 6.
Now for the selection we will start with the last cell. i.e. M[3][4]. For the whole weight of 4, the maximum capacity we can get is 6. Since this is the value for Pen.And the weight of pen is 1 we still have space for 3 weight.
We go to the column for 3 weight. The maximum here is again 6 which is the value for Pen. But since Pen is already taken. We cannot include it again.
The other item remaining is Eraser. The weight of eraser is 3. Hence we get the total weight of our knapsack as 1 + 3 = 4. And we get two items for the knapsack i.e Eraser and Pen.
Conclusion:
I know the post was long but it is worth understanding the knapsack algorithm before going to the interview of any good companies. Since this article is already too long, I will show you the practical code example where we can use this algorithm.
