Knapsack Problem (Dynamic Programming)

Problem statement

Let given weights & values of n items to be put in a knapsack of capacity W ie.

We’ve 2 integer arrays value[0..n-1] and weight[0…n-1]. The objective is to find out the maximum value subset of value[] array such that sum of weight of subset is smaller or equal to W.

Optimal Substructure

An optimal solution to problem contain optimal solution to subproblems. To consider all subset of items, 2 cases for every item arises:

  1. Item is included in optimal set
  2. Item is not included in optimal set

Therefore, max value obtained from n items is maximum of the following:

  1. Maximum value obtained by n-1 items and w weight, excluding nth item.
  2. Value of nth item + maximum value obtained by n-1 items and w – weight of nth item (including nth item). If weight of nth item is greater than W, nth item cannot be included.

Overlapping Subproblems

A recursive solution: (Top down approach)

int knapsack (int W, int wt[], int val[], int n) {

  //Base case
  if (n == 0 || W == 0) {
    return 0;
  } 

  if (wt[n-1] > W) {

    // Excluding item val[n-1]
    return knapsack(W, wt, val, n-1);
  } else {

    //including item val[n-1] if it results in greater value
    return max ((val[n-1] + knapsack(W-wt[n-1], wt, val, n-1)), 
                           knapsack(W, wt, val, n-1));
  }
}

Main function

int main () {

  int val[] = {60, 100, 120};
  int wt[] = {10, 20, 30};
  int W = 50, n = 3;

  printf("%d", knapsack(W, wt, val, n));

  return 0;
}

Here’s a running example: Recursive Knapsack

Understanding the problem in this approach

Here, certain subproblems are recomputed. Let’s see how,

wt[ ] = {1, 1, 1}, val[ ] = {10, 20, 30}, n=3, W = 2.

Now, K(n, W)

Overlapping Subproblems

Recomputations can be avoided by exploiting overlapping subproblems property ie. by constructing a temporary array K[n][W] in bottom up manner.

Here’s the code:

int knapsack (int W, int wt[], int val[], int n) {
  int K[n+1][W+1] = {0};

  // Building table K[n][W] in bottom manner
  for(int i=0; i<=n; i++) {
    for(int w=0; w <= W; w++) {

      // Base case: empty knapsack
      if (i == 0 || w == 0) {
        K[i][w] = 0;
      } else if (wt[i-1] <= w) {

        // Selecting val[i-1] if it gives higher knapsack value
        K[i][w] = max((val[i-1] + K[i-1][w-wt[i-1]]),
                   K[i-1][w]);
      } else {

        // Not including val[i-1]: if wt[i-1] is greater than 
        // available knapsack capacity
        K[i][w] = K[i-1][w];
      }
    }
  }
  return K[n][W];
}
 

Here’s a working example: Knapsack Solution

Time complexity of this solution is O(n*W).
In the next post, we’ll learn about, how to find the actual Knapsack items that were selected.
Adios!

3 thoughts on “Knapsack Problem (Dynamic Programming)

Leave a Reply

Your email address will not be published.