Consider solving the following Knapsack ILP by Discrete Dynamic Programming (DDP):

min 18x1 + 13x2 + 20x3 + 12x4 s.t. 2x1 + 6x2 + 4x3 + 3x4 Ú 14 x1, x2, x3, x4  [0, 2] and integer

(a) Define the states and stages of the DDP to compute an optimum.

(b) Draw a digraph from which an optimum can be computed over the states and stages of (a). How does it differ from similar digraphs for 0-1 Knapsack Problems like Figure 9.16?

(c) Solve the DDP depicted in (b), as it starts at the Finish node and proceeds backward to update values for each state and stage.

Then identify the optimal solution found.