 Solution

ID: 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 table

j \ b 01234 000000100000201515151530151818184015182121501533333360153336367015333940

(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

x^{*} = (1, 0, 0, 1), p^{T} x^{*} = 40.

Its weight is

2 + 5 = 7

. The recurrence proves that no binary selection with capacity seven has greater profit.

 New to topics? Read the docs here!