Dynamic Programming: The Knapsack Problem

Welcome to the 3rd part of my dynamic programming series. I will use dynamic programming and memoization to solve the Knapsack Problem.

The problem is as follows:

Given a knapsack with a maximum capacity of W and a list of items, select the items that fit inside the knapsack and yield the highest value.

Optimal Substructure and Recurrence Equation

Dynamic programming solves a hard problem by solving subproblems and combining the results. When a problem can be solved using dynamic programming, it is said to have an optimal substructure.

Let’s assume you win a one-time shopping experience with Jeff Bezos and are given a knapsack that can hold 5 lbs. If you have to choose between these three items:

Coffee machine — $5000– 5lbs

Macbook — $4000–3lbs

Rolex watch — $10,000–2lbs

What items would you add to your knapsack to get the maximum value?

For an item with weight Wj and value Vj, you can either take it or leave it. If you choose to take it, the new capacity of your knapsack is 5 — Wj, and the value of your knapsack increases by Vj.

The recurrence equation is the maximum between taking or leaving the current item:

The recurrence equation

Using the equation above, you can solve the problem with the following steps:

1. Determine the base cases: a) when the knapsack capacity is zero, the maxValue is zero. b) When the knapsack is over capacity, the value is negative infinity(a value that is not useful).
2. Call solve the recurrence equation.

def maxValue(W, j, weights, values):
    if W == 0: # basecase 1: no knapsack at all
        return 0
    if W < 0: # basecase 2: knapsack is out of capacity
        return -float('inf')
    if j >= len(weights): # the current item is not in the weights list
        return 0
    return max(values[j] + maxValue(W-weights[j], j+1, weights, values), maxValue(W, j+1, weights, values))
  

Memoize

You can optimize the maxValue function by storing and reusing previously calculated values in a two-dimensional table. Let’s create a table: the rows will be the items, and the columns have the knapsack capacity from 1lb to 5lb.

Starting from the coffee table row, you will fill the grid row by row until the final result.

Rolex row, 2lbs

The Rolex is the first item and therefore the only item to consider at this stage. It weighs 2lb and can fit in the 2lb, 3lb, 4lb, and 5lb knapsacks. Let’s add the value of the Rolex in the corresponding knapsack columns of the table.

The MacBook row, 3lbs

For the second row, you can pick the Rolex or the MacBook. The Macbook and Rolex won't fit into the 1lb knapsack. The MacBook is too heavy for the 2lb knapsack but the Rolex can fit, so you take the Rolex. The Macbook fits into the 3lb and 4lb knapsack but since the goal of the exercise is to maximize the value, you pick the Rolex in both columns. The 5lb knapsack can fit both the Rolex and MacBook.

The coffee maker row

In the third row, you can add the Rolex, the MacBook, or/and the Coffee maker. The 1lb knapsack can’t fit any of the items. The 2lb knapsack can fit the Rolex. The 3lb and 4lb knapsacks can fit the Rolex or the MacBook, but the Rolex has the highest value so you pick the Rolex. The 5lb knapsack can fit the Rolex and MacBook or only the coffee maker.

Writing the Code

The solution to the optimized version of maxValue is as follows:

1. Fill a 2D list with zeros and pass it to a variable, T. This will store the maxValue for each knapsack.
2. Fill another 2D list, S. For every cell, store 1 if you take the item in that cell and store 0 if you leave that item. That is, if the item is taken S[(knapsack, item)] = 1, else S[(knapsack, item) = 0.
3. Create a helper function to retrieve previously calculated maxValue from T.
4. Run two for-loops to fill T and S.
5. Retrieve the items to pick.

def memoizedMaxValue(W, weights, values):
    n = len(weights)
    if W == 0:
        return 0
    T = [[0 for j in range(n) ]for w in range(W+1)]
    S = [[0 for j in range(n) ]for w in range(W+1)]
    
    def retrieveTableEntry(i,j):
        if i == 0:
            return 0
        if i < 0:
            return -float('inf')
        return T[i][j]
  
    for i in range(1, W+1):
        for j in range(n-1, -1, -1):
            T[i][j], S[i][j] = max((values[j] + retrieveTableEntry(W-weights[j], j+1),1), (retrieveTableEntry(W-weights[j], j+1),0))
    
    itemsToPick = []
    weight = W
    for j in range(n):
        if S[weight][j] == 1:
            itemsToPick.append(j)
            weight = weight - weights[j]
     return T[W][0], itemsToPick