= Solution
Applying the recurrence in source item order gives the complete table
$$
\begin{array}{c|rrrrrrrr}
j\backslash b&0&1&2&3&4&5&6&7\\\hline
0&0&0&0&0&0&0&0&0\\
1&0&0&15&15&15&15&15&15\\
2&0&0&15&18&18&33&33&33\\
3&0&0&15&18&21&33&36&39\\
4&0&0&15&18&21&33&36&40
\end{array}
$$
At $(4,7)$ inclusion wins, since $25+D(3,2)=40>D(3,7)=39$. Thus $x_4=1$ and the residual capacity is two. Items three and two are too heavy for it, and item one exactly fits. Consequently
$$
\boxed{x^*=(1,0,0,1),\qquad p^Tx^*=40.}
$$
Its weight is $2+5=7$. The recurrence proves that no binary selection with capacity seven has greater profit.
Back to article page
