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.