Summary: In this tutorial, we will learn how to solve 01 Knapsack Problem using dynamic programming algorithm in C++ and Java.

Introduction to 0-1 Knapsack Problem


The knapsack problem is a problem in combinatorial optimization: Given a set of items, each with a weight and a value, determine the number of each item to include in a collection so that the total weight is less than or equal to a given limit and the total value is as large as possible

https://en.wikipedia.org/wiki/Knapsack_problem

For example, consider the following 4 weights each having different values.

01 knapsack program using dynamic programming

A knapsack bag has a total weight limit of 5, we need to find the number of each weight to include in the bag for the maximum total value.

In the 0-1 Knapsack Problem, we are only allowed to take items in whole numbers. i.e. we cannot take items in the fractions.

Let’s discuss how can we solve 01 knapsack problem.

0-1 Knapsack Problem solution using DP

Though the 0-1 Knapsack problem can be solved using the greedy method, using dynamic programming we can solve it more efficiently and faster.

Recommended:

To solve the knapsack problem using dynamic programming, we have to memorize the solution of the subproblems.

Now the question is what is the subproblem here?

Look at the following naive approach of solving the knapsack problem using recursion:

Knapsack problem in C++
01 Knapsack recursive solution

In the recursive approach, we are making two successive recursive calls within the function i.e.:

  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.

Two recursive calls exponentially increases the time complexity to O(2n).

By using the concept of dynamic programming we can store solutions of the repetitive subproblems into a memo table (2D array) i.e. instead of using KS(n-1, C), we will use memo-table[n-1, C].

By using the memoization technique, we can reduce 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: The size of the memo table is  (Total number of items + 1) * (Knapsack Weight+1).

In the memo table:

  • Row –  is the number of items we can take. The first row is 0, it means no item is available. The second row is 1, it means only the 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 the total value for the given knapsack weight.
  • Column – is the knapsack weight. The first column is 0, it means the knapsack bag is not available. The second column is 1. it means the value of knapsack weight is 1, therefore we can only take those items whose total weights sum up to 1. The fourth column (Last column) is 5, which is what we want, the total weight in the knapsack bag.

Each table cell stores solution of subproblems. For e.g. memo-table[3][2] = 21.

memo-table[3][2] = 21 means for a kanpsack bag of weight equal to 2, the maximum value that can be achieved with first 3 items is 21.

As we have a memo table available with us, we will use a normal function with for loop to loop through all the indexes in the memo table.

While iterating we will use the previously stored values in the table to calculate the values of the current table cell.

Let’s see how the program for the 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 the last (selected) item from j and repeat the same process for the resultant value of the 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

Dynamic Program C

In this tutorial, we learned to solve the 01 knapsack problem using Dynamic programming algorithm.

Leave a Reply