Knapsack

Given:

• n items
• Weights $w_1,w_w,w_3,\dots ,w_n$
• Values $v_1,v_2,v_3,\dots ,v_n$

You can carry a total weight of at most $W$. What is the most valuable combination of items that you can fit into your knapsack.

With Repetition

There is an unlimited supply of each item. We care about value per weight here. This is the shoplifter example.

Sub problem

• Define $K(\bar{w})=\text{max value with capacity }\bar{w}$, where $\bar{w}<W$
• The goal is do compute $K(W)$
• Suppose the optimal solution to $K(\bar{w})$ includes item i
• Then removing i from the solution must be an optimal solution to $K(\bar{w}-w_i)$
• Therefore, $K(\bar{w})=K(\bar{w}-w_i)+v_i$
• The base case here is a knapsack of capacity has no value

K(0)=0
for w = 1...W:
	K(w) = max_{i:w_i<w}{K{w-w_i}+v_i}
return K(w)

The runtime here is $O(nW)$ due to the dynamic max operation within the loop. This problem scaled with the value of W so this is a pseudopolynomial algorithm.

Without Repetition

There is only one of each item. We need to keep track of what item has been used for a partial solution since that affects what can be added. $K(\bar{w})=K(\bar{w}-w_i)$ isn’t helpful since i might have been used in a previous solution. We need to keep track of a 2nd parameter j to subproblems.

Sub problem

• $K(w,j)$ = $\text{max value with capacity }\bar{w}\text{ and items 1,2,...,j}$
• Answer to the problem is $K(W,n)$
• If $w_j>w$ then $K(w,j)=K(w,j-1)$
• Otherwise $K(w,j)=maxk(w,j-1),v_j+K(w-w_j,j-1)$
• Similarly, the base is is when the knapsack has no capacity which is 0

Initialize all K(0, j) = 0 and all K(w, 0) = 0

for j = 1, ..., n:
    for w = 1, ..., W:
        if w_j > w:
            K(w, j) = K(w, j - 1)
        else:
            K(w, j) = max {
                K(w, j - 1),
                K(w - w_j, j - 1) + v_j
            }

return K(W, n)

The runtime here is $O(nW)$.