Past exam of the integer programming course of the University of Oxford / 2011 / 2 / a / Solution

Let item $j$ have weight $a_j$ and profit $p_j$. Define $D(j,b)$ as the largest profit obtainable from the first $j$ items with capacity at most the nonnegative integer $b$. Set $D(0,b)=0$. The last item is either absent or present once, giving the dynamic programming recursionThe two alternatives exhaust the feasible binary decisions. In the second alternative, deleting item $j$ leaves exactly the smaller subproblem with capacity $b-a_j$, which proves the recurrence.

Fill rows $j=1,\dots ,4$, and within each row capacities $b=0,\dots ,7$. Store which alternative attains each maximum. Backtrack from $(4,7)$: when exclusion was chosen, set $x_j=0$ and move to $(j-1,b)$; when inclusion was chosen, set $x_j=1$ and move to $(j-1,b-a_j)$. Ties may be resolved either way. Thus the stored values yield an actual optimal selection, not just its objective value.

For $n$ items and capacity $B$, the algorithm uses $O(nB)$ arithmetic operations and $O(nB)$ space with the full backtracking table. It is a pseudo-polynomial algorithm, since $B$ is a numerical capacity rather than its bit length. A value-only version can use one row, but must update capacities in decreasing order to avoid reusing the same item.