= 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> recursion
$$
\boxed{D(j,b)=\begin{cases}
D(j-1,b),&b<a_j,\\
\max\{D(j-1,b),p_j+D(j-1,b-a_j)\},&b\geq a_j.
\end{cases}}
$$
The 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,\ldots,4$, and within each row capacities $b=0,\ldots,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 time>[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.
Back to article page
