A copy machine repairman has four pieces of test equipment for which he estimates 25%, 30%, 55%, and 15% chances of using them at his next stop. However, the devices weigh 20, 30, 40, and 20 pounds, respectively, and he can carry no more than 60 pounds. The repairman seeks a maximum utility feasible collection of devices to carry with him.

(a) Explain why this problem can be approached by discrete dynamic programming, with stages k = 1,

c, 4 representing the four devices and states w = 0, 10, 20, 30, 40, 50, 60 in each stage indicating reaching that decision stage with w units of weight limit remaining.

(b) Sketch the digraph corresponding to the dynamic program structure of part (a).

Include objective function contributions on all arcs.

(c) Explain why the feasible production plans correspond exactly to the paths from stage k = 1, state w = 60 to the last stage in your digraph.

(d) Solve a longest path problem on your digraph to compute an optimal toolkit.