Summary: In this tutorial, we will learn What is 0-1 Knapsack Problem and how to solve the 0/1 Knapsack Problem using Dynamic Programming.

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 we are given the following 4 weights with respective values.

01 knapsack program using dynamic programming

We are also given a knapsack bag that has a total weight limit of 5.

We have to find the number of each weight to include in the bag so that the total weight is less than or equal to 5 and the total value is as large as possible.

Note: We cannot include the faction of the item, we either include the whole single item or not.

There are multiple ways to solve the 0-1 Knapsack problem, one such method is recursion.

0-1 Knapsack Solution using Recursion (Inefficient Approach)

For each item, we have to decide whether to include it in the knapsack bag.

choose an item

To make this decision, we compare the total value of the bag when including the item with the value when not including the item.

Since for every item we have to repeat the same process, we use recursion.

The above program has two successive recursive calls within the function:

  1. knapsack(n-1, KW) – Total value when not including the nth item.
  2. knapsack(n-1, KW – weight[n]) – Total value when including the nth item.

This exponentially increases the time complexity of the program to O(2n).

We can definitely improve the efficiency of our program by incorporating other techniques.

The 0-1 Knapsack problem can be solved using the greedy method however using dynamic programming we can improve its efficiency.

0-1 Knapsack Solution using Dynamic Programming

The idea is to store the solutions of the repetitive subproblems into a memo table (a 2D array) so that they can be reused i.e., instead of knapsack(n-1, KW), we will use memo-table[n-1, KW].

But, what is the subproblem here?

For instance, when deciding on the 4th item (whether to include it or not) we recursively make decisions for all the preceding items (i.e., 3rd, 2nd, and 1st items) twice.

recursive calls in 01 knapsack problem

When deciding on the 3rd item, the decisions of the preceding items are made once again, although they were computed initially while making the decision for the 4th item.

This computation of the maximum value for the nth item is the subproblem here, which is computed repeatedly.

When calculated for the first time we store the corresponding value of Knapsack(N-1, KW) into the memo table and reuse if needed

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 the solution of a subproblem. For instance, memo-table[3][2] = 21 means for a knapsack bag of weight equal to 2, the maximum value that can be achieved with the first 3 items is 21.

As we have a memo table available with us, we iterate through its cells and use the previously stored values to calculate the values for the current cell.

Here is the implementation of the discussed dynamic programming solution:

C++

Java

The time complexity of the program is O(n2) i.e, much better than the recursive solution.

How to know which item is included in the bag?

To know which item is selected for calculating total Benefit/Value, start from the 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 0-1 knapsack problem using the dynamic programming algorithm in C++ and Java programming languages.

Leave a Reply

fourteen + one =