Consider the following Binary Knapsack Problem (BKP) instance max 7x1 + 9x2 + 21x3 + 15x4 s.t. 8x1 + 4x2 + 12x3 + 7x4 … 19 1BKP2 x1,

c, x4 = 0 or 1

(a) Construct the corresponding Dynamic Programming digraph (like Figure 9.16), including showing objective function coefficients on all arcs needed.

(b) What are the stages and what are the states of your model in (a)? Explain.

(c) Starting with state 19, stage 1 initialized with objective value v[19, 1] = 0, and taking each later stages in turn, compute optimal subproblem values v[state, stage]

for each reachable state and state.

(d) Use your results of

(c) to identify an optimal solution to the full instance and determine its objective function value.