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

Applying the recurrence in source item order gives the complete tableAt $(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. ConsequentlyIts weight is $2+5=7$. The recurrence proves that no binary selection with capacity seven has greater profit.