Question

Consider the problem of making change for n cents using the fewest number of coins. Assume that each coin’s value is an integer.

a) Describe a greedy algorithm to make change consisting of quarters, dimes, nickels, and pennies. Prove that your algorithm yields an optimal solution.
b) Give a set of coin denominations for which the greedy algorithm does not yield an optimal solution. Your set should include a penny so that there is a solution for every value of n.
c) Give an ()-time algorithm that makes change for any set of k different coin denominations, assuming that one of the coins is a penny. (Hint: using dynamic programming)

Answer 1

The greedy algorithm for making change is described and proven to yield an optimal solution. It is also explained how the greedy algorithm may not be optimal in certain cases. Lastly, an O(nk) algorithm using dynamic programming is suggested for making change with a set of k different coin denominations.

Step-by-step explanation:

(a) The greedy algorithm for making change is as follows:

1. Start with the largest coin value (quarters) and check if the value of the coin is less than or equal to the remaining change. If it is, subtract the value of the coin from the remaining change and increment the count of that coin.
2. Repeat this process for each coin denomination in decreasing order of value.
3. Return the count of each coin denomination.

To prove that this algorithm yields an optimal solution, we need to show that it always produces the minimal number of coins for any amount of change.

We can prove this by contradiction. Suppose that the greedy algorithm does not yield an optimal solution for some amount of change. This would mean that there exists another solution that uses fewer coins.

However, this is not possible because the greedy algorithm always chooses the largest coin denomination possible, which ensures that the remaining change is minimized.

Therefore, the greedy algorithm yields an optimal solution for making change.

(b) The greedy algorithm does not yield an optimal solution if the coin denominations include a coin that is not a multiple of the other coin denominations. For example, if we include the penny as one of the coin denominations, the greedy algorithm may not yield the optimal solution for certain amounts of change.

(c) An O(nk) algorithm can be used to make change for any set of k different coin denominations, assuming that one of the coins is a penny. This algorithm can be implemented using dynamic programming.