0-1 Knapsack Problem

In this tutorial we will be learning about 0 1 Knapsack problem. In this dynamic programming problem we have n items each with an associated weight and value (benefit or profit). The objective is to fill the knapsack with items such that we have a maximum profit without crossing the weight limit of the knapsack. Since this is a 0 1 knapsack problem hence we can either take an entire item or reject it completely. We can not break an item and fill the knapsack.

Point to remember

• In this problem we have a Knapsack that has a weight limit W.
• There are items i1, i2, ..., in each having weight w1, w2, … wn and some benefit (value or profit) associated with it v1, v2, ... vn
• Our objective is to maximise the benefit such that the total weight inside the knapsack is at most W.
• Since this is a 0 1 Knapsack problem algorithm so, we can either take an entire item or reject it completely. We can not break an item and fill the knapsack.

Problem

Assume that we have a knapsack with max weight capacity W = 5
Our objective is to fill the knapsack with items such that the benefit (value or profit) is maximum.

Following table contains the items along with their value and weight.

Total items n = 4
Total capacity of the knapsack W = 5

Now we create a value table V[i,w] where, i denotes number of items and w denotes the weight of the items.
Rows denote the items and columns denote the weight.
As there are 4 items so, we have 5 rows from 0 to 4.
And the weight limit of the knapsack is W = 5 so, we have 6 columns from 0 to 5

We fill the first row i = 0 with 0. This means when 0 item is considered weight is 0.

Then we fill the first column w = 0 with 0. This means when weight is 0 then items considered is 0.

Rule to fill the V[i,w] table.

if wt[i] > w then
V[i,w] = V[i-1,w]

else if wt[i] <= w then
V[i,w] = max( V[i-1,w], val[i] + V[i-1, w - wt[i]] )

After calculation, the value table V

Maximum value earned
Max Value = V[n,W]
= V[4,5]
= 140

Items that were put inside the knapsack
are found using the following rule

set i = n and w = W

while i and w > 0 do
  if V[i,w] != V[i-1,w] then
    mark the ith item
    set w = w - wt[i]
    set i = i - 1
  else
    set i = i - 1
  endif
endwhile

So, items we are putting inside the knapsack are 4 and 1.

C Code

#include<stdio.h>

void knapSack(int W, int n, int val[], int wt[]);
int getMax(int x, int y);

int main(void) {

  //the first element is set to -1 as
  //we are storing item from index 1
  //in val[] and wt[] array
  int val[] = {-1, 100, 20, 60, 40};  //value of the items
  int wt[] = {-1, 3, 2, 4, 1};        //weight of the items
  
  int n = 4;  //total items
  int W = 5;  //capacity of knapsack
  
  knapSack(W, n, val, wt);

  return 0;
}

int getMax(int x, int y) {
  if(x > y) {
    return x;
  } else {
    return y;
  }
}

void knapSack(int W, int n, int val[], int wt[]) {
  int i, w;

  //value table having n+1 rows and W+1 columns
  int V[n+1][W+1];

  //fill the row i=0 with value 0
  for(w = 0; w <= W; w++) {
    V[0][w] = 0;
  }

  //fille the column w=0 with value 0
  for(i = 0; i <= n; i++) {
    V[i][0] = 0;
  }

  //fill the value table
  for(i = 1; i <= n; i++) {
    for(w = 1; w <= W; w++) {
      if(wt[i] <= w) {
        V[i][w] = getMax(V[i-1][w], val[i] + V[i-1][w - wt[i]]);
      } else {
        V[i][w] = V[i-1][w];
      }
    }
  }

  //max value that can be put inside the knapsack
  printf("Max Value: %d\n", V[n][W]);
}

Time complexity

Time complexity of 0 1 Knapsack problem is O(nW) where, n is the number of items and W is the capacity of knapsack.