In 0 1 Knapsack Problem, we are allowed to take items only in whole numbers. i.e we cannot take items in the fractions just to make knapsack bag completely full. Though 0 1 Knapsack problem can be solved using the greedy method, by using dynamic programming we can make the algorithm more efficient and fast.

If you don’t know, then you must read:

0 1 knapsack problem

We are given 4 weights with different values and told to fill knapsack bag of  5.

01 knapsack program using dynamic programming

As we know that to solve the knapsack problem using dynamic programming technique, we require to memoize (not memorize) the solution of the subproblems.

Now the Question is what is subproblem here?

Look at the naive approach of solving knapsack problem using recursion.

Knapsack problem in C++

In a normal recursive approach, we have to make another two recursive call within the recursive function.

  1. KS(n-1, C) – Total value when not taking the nth item.
  2. v[n] + KS(n-1, C – w[n]) – Total value when already took nth item.

Thus the time complexity becomes O(n*n*n).

By using the concept of dynamic programming we can store the each of the subproblem into memo table (2D matrix). Hence instead of using KS(n-1, C) , we will use memo-table[n-1, C]. Thus reducing the computational work to large extent.

Now the question arises, how the memo table will look like or supposed to have?

knapsack problem using Dynamic Programming

Note: Size of the memo table is  (Total number number of items + 1) * (Knapsack Weight).

In the memo table:

  • Row –  is the number of items we can take. First row is 0, it means no items is available. Second row is 1, it means only 1st item is available. Similarly, Third row is 2, it means only 1st and 2nd item are available….Forth row tells that all 4 items should be considered for computing total value for a particular given knapsack weight.
  • Column – is the knapsack weight. First column is 0, it means knapsack bag is not available. Second column is 1. it means the value of knapsack weight is 1, so we can take only those items whose weights sum up to 1……Forth column (Last column) is 5, which is what we want, the total weight in the knapsack bag.

Thus each table field is storing the solution of sub problems. For e.g memo-table[3][2] = 21 , it means the total value which can be obtained from 3 items (first three) of different weights when knapsack weight is equal to 2 is 21.

Now, we have a memo table available with us, so no more recursive calls are required, hence we will use a normal function with the loops.

We will loop through all the indexes in the memo table and make use of previously stored solutions of the subproblems.

So lets see how the program for 0-1 Knapsack problem looks like.

0 1 Knapsack Problem in C++| Java

C++

Java


How to know which item is taken/selected?

To know which item is selected for calculating total Benefit/Value, start from last row and column index. Go one level up and check whether the value in the upper level is smaller or not.

  • If YES, then it means that the difference is caused because of including the last item (4th item in our case). Now subtract the weight of last (selected) item from j and repeat the same process for the resultant value of jth column.
  • If NO, then go one level up more and check for the difference in the value. Keep going up until you see the difference in the value.

01 knapsack problem dynamic programming

Output of Program

Dynamic Program C

That’s all we need to write a program to solve 01 Knapsack problem using dynamic programming. If you have any doubt then comment below. I will help.

Leave a Reply

Close Menu