Knapsack Problem

Suppose you had a thief who broke into a house and saw a bunch of stuff to steal. Unfortunately, his thief knapsack can only hold 20 pounds, and each of the things to steal weighs some amount, and has some amount of monetary value. The thief wants to maximize his "bang for the buck" and thus gather as much value for the 20 pounds of knapsack he has.

Specifically, for weights[] and values[], the ith object the thief sees has a weight of weights[i] and a value of values[i]. What's the maximum value he can get with some maxWeight pounds?

So for example, if weights = [10, 5, 6] and values = [20, 5, 6], while maxWeight = 20, he can get a maximum value of 26 with a weight of 16 (he picks the 0th and 2nd items). How would you write a program to solve for many items, and a large maximum weight?

• Hint

  There is no analytic way to solve this, unfortunately - you have to brute force it. But there are a few interesting properties of the problem that allow us some room to be clever.

  One interesting property is that there are a lot of overlapping subproblems here - the "big" solution can be derived from solutions of smaller problems.

  From this property, we can intelligently brute force this problem using the technique of dynamic programming, which means building a table of values, and filling in the later entries of the table using the earlier entries of the table, where the earliest entries of the table are a specifically defined base case.

• Solution

  There isn't a known analytic way to solve this problem, but we note that the problem can be broken down in 2 different dimensions. One break the problem down by weight by saying, "What if the thief could only carry 1 pound? What about 2 pounds? 3 pounds?" One could also break it down by items by saying, "What if the thief only knew about the first 2 items? first 3 items?" Now we know we can use dynamic programming to use those broken down solutions to find our desired, big solution for all values and maximum weight.

  Base Case

  Most dynamic programming problems, including this one, require a base case. In this problem, the base case is fairly intuitive. We know for sure that if the thief has a maximum weight of 0, then he can't get any value at all. We also know that if he has seen 0 items, then he also can't get any value. This is our starting point.

  Recurrence Relation

  This is the heavy part of the explanation, so follow closely. We're going to make a table to hold all of our little solutions - we'll call this table dp. We'll say that dp is two dimensional, like a basic Excel spreadsheet. Let's say the number of rows = the length of values[] + 1 (the +1 is to account for the base case) and the number of cols = maximum weight. Notice that this lines up with our supposing in the introductory paragraph, "What about 2,3,4 pounds? What about 1st, 2nd, 3rd items?" etc.

  First we define what each entry in the table means. dp[i][j] for all i, j indices in the table is equal to the maximum value that the thief can obtain having looked at the first i items, and constrained by j maximum weight.

  Now we have to form the recurrence relation which describes how we combine the subproblems into the big solution. As we look at each next item, if the item's weight is larger than j (our max weight), then we can't take it because it's too heavy - we have to leave it. If it's not larger than j, then we can either take it or leave it. If we take it, then we take the best solution we had for j - weight[i - 1], + the value of the item we took, such that takeIt = dp[i][j - weights[i - 1]] + values[i - 1]. Why weights[i - 1] and values[i - 1]? Because we augmented our table for the base case. If we leave it, then our best value is what we had the last time (see how we're tapping into our subproblems?) so dp[i][j] = dp[i - 1][j]. We want the maximum score between taking it and leaving it. So the algorithm is as follows:

                  is j >= weights[i - 1]?
                    yes:
                      takeIt = dp[i][j - weights[i - 1]] + values[i - 1];
                      leaveIt = dp[i - 1][j];
                      dp[i][j] = max(takeIt, leaveIt);
                    no:
                      dp[i][j] = dp[i - 1][j]
                

  Pseudocode Solution

  Supposing we have maximum weight set to 20, values as [20, 5, 6] and weights as [10, 5, 6]:

                  values = [20, 5, 6]
                  weights = [10, 5, 6]
                  MAX_WEIGHT = 20
  
                  dp = array[values.length + 1][MAX_WEIGHT + 1]
                  numRows = values.length + 1
                  numCols = MAX_WEIGHT + 1
  
                  # Loop through the rows and columns
                  for i in [0...numRows]:
                    for j in [0...numCols]:
                      # Establish the base case
                      if i == 0 or j == 0:
                        dp[i][j] = 0
                        continue;
  
                      # Use the recurrence relation
                      if j >= weights[i - 1]:
                        takeIt = dp[i - 1][j - weights[j - 1]] + values[i - 1]
                        leaveIt = dp[i - 1][j]
                        dp[i][j] = max(takeIt, leaveIt)
                      else:
                        dp[i][j] = dp[i - 1][j]
  
                  print "the maximum value the thief can get with his knapsack is " + dp[values.length][MAX_WEIGHT]
                

  Seems like magic.

Home