4) Consider the problem of making change for V cents using the fewest number of coins....

Transcribed Image Text:

4) Consider the problem of making change for V cents using the fewest number of coins. Suppose that the denominations of the k + 1 available coins are powers of c, for a positive integer c > 1. That is, the denominations are c, c1, c2, ..., ck for k > 1. a) Find the optimal solution for c = 5, k = 2 and V = 99. b) Describe a greedy algorithm for making change for V cents with the denominations co, c1, c2, ..., ck for integers c > 1 and k > 1. c) Prove that the greedy algorithm always yields an optimal solution. 4) Consider the problem of making change for V cents using the fewest number of coins. Suppose that the denominations of the k + 1 available coins are powers of c, for a positive integer c > 1. That is, the denominations are c, c1, c2, ..., ck for k > 1. a) Find the optimal solution for c = 5, k = 2 and V = 99. b) Describe a greedy algorithm for making change for V cents with the denominations co, c1, c2, ..., ck for integers c > 1 and k > 1. c) Prove that the greedy algorithm always yields an optimal solution.