2. Youre walking along the beach and you stub your toe on something in the sand. You dig around it and find that it is a treasure chest of k gold bricks of different (integral) weight. Your knapsack can only carry up to weight n before it breaks apart. You want to put as much in it as possible without going over, but you cannot break the gold bricks up.

(a) Suppose that the k gold bricks have the weights 1, 2, 4, 8, . . . , 2 k1 , for k 1. Describe a greedy algorithm that fills the knapsack as much as possible without going over.

(b) Prove that your algorithm is correct.

(c) Give an example, including a multiset of different weight values of bricks and total weight n that the knapsack can carry up, for which the greedy algorithm does not yield an optimal solution