# Knapsack Problem

A thief has a knapsack, but it has a weight capacity w. The sum of the weight of the goods must be under w.

Consider the items: [1..n] with weight [W1..Wn] and value [V1..Vn]

Maximize the dollar value of the stolen goods without tearing the knapsack.

Approach: consider each item and decide to take it or leave it.

# Approach

For each item i, take it or leave it.

If you take it, adjust value with Vi and weight with w - Wi. What remains is a subproblem that looks like the original problem but with different values.

recurrence:

maxValue(j, W (capacity limit)) {
    0 if W is 0
    -inf if W is < 0
    0 j == n + 1
    max {
        Vj + maxValue(j+1, W - wj) <- take it
        maxValue(j+1, W) <- leave it
    }
}

How to memoize?

Design a table with width and height of n. The first row and column will be all zeros. Each sub problem is looking at one row below and either w or w - Wj. Fill up each row left to right from bottom to top.

Running time: Θ(nW0)

W0 is the actual magnitude, so if W0 = 10,000 then n^5

Called pseudo polynomial, exponential time referenced to the magnitude defined by W.

Rebuilding solution: at each j record if you took or left, then trace back through your table.

def maxSteal_memo(W, weights, values):
    # Initialize the tables
    T = [0]* (W+1)
    S = [-1]* (W+1)
    k = len(weights)
    assert len(values) == k
    for w in range(1, W+1):
        opts =  [  ( (values[i]+ T[ w - weights[i] ]), i )  for i in range(k) if w - weights[i] >= 0 ]
        opts.append( (-float('inf'), -1) ) # In case opts was empty from the previous step.
        T[w], S[w] = max(opts)
    # This finishes the computation
    stolen_item_ids = []
    weight_remaining = W
    while weight_remaining >= 0:
        item_id = S[weight_remaining]
        if item_id >= 0:
            stolen_item_ids.append('Steal Item ID %d: weight = %d, value = %f' % (item_id, weights[item_id], values[item_id]) )
            weight_remaining = weight_remaining - weights[item_id]
        else:
            break
    return T[W], stolen_item_ids