You have a long sequence of n items, where each item i has a corresponding weight wi . All weights are positive integers, and a weight greater than 50 means that the item is considered heavy. You want to pick up items whose total weight is as large as possible, however: you are picking up the items from left to right (in sequence order), and if you pick up a heavy item then you will be unable to pick up the item immediately after it.

(a) Consider the greedy algorithm that considers the integers from left to right, and picks up each item as long as the rules allow it (either the preceding item was not picked up, or it was not heavy). Give and demonstrate a counterexample to show that this greedy algorithm does not always work.

(b) Design and write (in pseudocode) a dynamic programming algorithm that computes the largest possible total weight allowed from the given input.

(c) Modify your algorithm from (b) to extract the subsequence that produces the optimum.