Let's rob a store, shall we?

Dynamic Programming, Optimization

Originally posted on Oct 20, 2014 in my previous blog.

Suppose we decide to rob a store for for fun :P. Before making a fool out of ourselves during the robbery, we have a make a plan A, a plan B if ‘A’ fails, a plan C if ‘B’ fails… and so on.

The great Le Marc (apparently he is an awesome thief in Ocean’s Twelve movie) wants to help us out and makes all the entry and exit strategies. But leaves the work of actually stealing the items to us. Of course we are greedy and want to get as much value items as possible. But there is a limit on the weight a person can carry (C’mon we are only human). Moreover we are Computer Science Engineers and we love everything to be optimal.

The 0 - 1 knapsack problem

There are different items in the store, each item is valued differently and has a different weight. Now our job is to rob the place in such a manner that we get the highest loot. What items should we take? The most valued item may in fact weigh a lot. And Le Marc has imposed another condition on us, we have a rob an item as a whole, we cannot break it.

Solution

A greedy approach does not solve our problem (Why? take an example and try it out). In the 0-1 knapsack problem, we have to decide whether to include an item (in the knapsack) or not. The original problem consists of subproblems- one that includes an item with the solution and another which does not include the particular item. This forms many overlapping sub-problems and can be solved using dynamic programming.

Recursion and memoization

Let w[] denote the weights of the items and v[] denote the values of those items. Suppose that we have a knapsack that can carry only upto wt weight and n is the number of items. Then, the recursive solution can be written as

int knapsack(int w[], int v[], int wt, int n) {
  if(wt == 0 || n == 0)
    return 0;

  if(w[n - 1] > wt)
    return knapsack(w, v, wt, n - 1);
  else {
    return max(v[n - 1] + knapsack(w, v, wt - w[n - 1], n - 1),
               knapsack(w, v, wt, n - 1));
  }
}
                  

This can be easily be improved by using memoization. Initialize a 2d array knapsack[n+1][wt+1] with ‘0’. knapsack[i][j] represents the maximum value that can be obtained from the first ‘i’ items and maximum weight=j.

for(i = 0; i <= n; i++) {
  for(j = 0; j <= wt; j++) {
    if(i == 0 || j == 0) {
      knapsack[i][j] = 0;
    } else if(w[i-1] <= j) {
      knapsack[i][j] = max(v[i-1] + knapsack[i - 1][j - w[i - 1]],
                           knapsack[i - 1][j]);
    } else {
      knapsack[i][j] = knapsack[i - 1][j];
    }
  }
}