0-1 Knapsack Problem using Dynamic Programming

Algorithm

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.

#include <iostream>
//Weights
int weight[] = {0, 1, 2, 1, 3};
//values
int value[] =  {0, 10, 7, 11, 15};

//recursive funciton
int knapsack(int n, int KW){
  //base condition
  if(n<=0 || KW<=0)
    return 0;
  //don't select item if its weight is greater than knapsack weight
  else if(weight[n]>KW)
    return knapsack(n-1, KW);
  //check which gives more value
  //1. When not including the nth item
  //2. When including the nth item 
  else{
    //total value when not including the item
    int not_include_nth_item = knapsack(n-1, KW);
    //total value when including the item
    int include_nth_item = value[n] + knapsack(n-1, KW-weight[n]);
    //return the larger value
    return std::max(not_include_nth_item, include_nth_item);
  }
}

//Driver code
int main() {
  //knapsack(<number_of_items>, <knapsack_weight>)
  std::cout << knapsack(4, 5);
}

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++

#include <iostream>
#define MAX 200
using namespace std;

//weights
int weight[] = {0, 1, 2, 1, 3};
//values
int value[] =  {0, 10, 7, 11, 15};
//knapsack bag weight limit
int knapsack_weight = 5;
//count of items
int n = 4;

class KnapsackDP{
public:
  int **memoTable;

  KnapsackDP(){
    // memo table
    this->memoTable = new int*[n+1]; 
    //Initiale each cell with 0
    for(int i=0; i<n+1; i++){
        this->memoTable[i]= new int[knapsack_weight+1] {0};
    }
  }

  int solve(){
    //Compute and fill the memo table
    for(int i=1; i< (n + 1); i++){
      for(int j=1; j<(knapsack_weight + 1); j++){
        //when not including the item
        int not_taking_item = memoTable[i-1][j];
        //when including the item
        int taking_item = 0;
        if(weight[i] <= knapsack_weight){
          if(j-weight[i] < 0)
              taking_item = memoTable[i-1][j];
          else
              taking_item = value[i] + memoTable[i-1][j-weight[i]];
        }

        //store the larger value in the table
        memoTable[i][j] = max(not_taking_item, taking_item);
      }
    }
    //return the max value for the given knapsack weight
    return memoTable[n][knapsack_weight];
  }

  //Function output the included items
  void selected_items(){
    for(int i=n, j= knapsack_weight; i>0; i--){
      if(memoTable[i][j] != memoTable[i-1][j]){
        cout << "Item: "<<i <<" Selected \n";
        j = j- weight[i];
      }
    }
  }
};
 
int main()
{
  KnapsackDP kdp;
  cout << "Total Benefit: "<< kdp.solve() <<endl;

  //To print which items are included
  kdp.selected_items();
  return 0;
}

Java

public class Main{
  public static void main(String args[]){
    //weights
    int weight[] = {0, 1, 2, 1, 3};
    //values
    int value[] = {0, 10, 7, 11, 15};
 
    //Taking Knapsack weight as 5
    KnapsackDP kdp = new KnapsackDP(5, 4, weight, value);
    System.out.println("Total Benefit: "+kdp.solve());
 
    //To print which items are selected
    kdp.selected_items();
  }
}
 
class KnapsackDP{
  int knapsack_weight;
  int n;
  int weight[];
  int value[];
  int memoTable[][];
 
  public KnapsackDP(int W,int N,int weight[],int value[]){
    this.knapsack_weight = W;
    this.n = N;
    this.weight = weight;
    this.value = value;
    this.memoTable = new int[N+1][W+1];
  }
 
  public int solve(){
    //compute and fill the table
    for(int i=1; i< (n + 1); i++){
      for(int j=1; j<(knapsack_weight + 1); j++){
        //when not including the item
        int not_taking_item = memoTable[i-1][j];
        //when including the item
        int taking_item = 0;
        if(weight[i] <= knapsack_weight){
          if(j-weight[i] < 0)
              taking_item = memoTable[i-1][j];
          else
              taking_item = value[i] + memoTable[i-1][j-weight[i]];
        }
 
        //store the larger value in the memo table
        memoTable[i][j] = Math.max(not_taking_item, taking_item);
      }
    }
    //return the max value for the given knapsack weight
    return memoTable[n][knapsack_weight];
  }
  
  //Function to output included items
  public void selected_items(){
    for(int i=n, j= knapsack_weight; i>0; i--){
      if(memoTable[i][j] != memoTable[i-1][j]){
        System.out.println("Item: "+i+" Selected");
        j = j- weight[i];
      }
    }
  }
}

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(memoTable[i][j] != memoTable[i-1][j])
  • 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

Your email address will not be published. Required fields are marked *