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 contains 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 with remaining ‘W’ knapsack weight capacity (excluding the n^th item).
2. Value of n^th item + maximum value obtained by n-1 items and with ‘W – weight of the n^th item’ remaining knapsack weight capacity (including the n^th item).
3. If weight of n^th item is greater than W (remaining knapsack capacity value), n^th 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)

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.