Optimal Coin Change Problem

Given an unlimited supply of coins of denominations C1, C2, ..., CN we wish to make change for a value V. Give an algorithm for producing change with minimum number of coins.

Complexity: Depending on denomination of coins, we can either use fast greedy algorithm or dynamic programming.

Solution:
Consider two specific types of denominations of coins
a) 1, C, C^2, C^3, ..., C^(N-1)
b) 1, C, 2C, 3C, ...., (N-1)C

For both of these arrangements, the problem can be solved using a greedy approach. We see that if we first pay with the highest denomination coin, the value (for which change is required) reduces greatest (as compared to any lower denomination). Additionally we see that optimal solution would require us to use as many highest denomination coin as possible. We can prove this claim using contradiction. The greedy algorithm that is pretty fast and runs in O(N), is as follows:

change = 0
for j = N to 1
  change += int(value/C[j])
  value = value % C[j]
return change

The generic problem of coin change cannot be solved using the greedy approach, because the claim that we have to use highest denomination coin as much as possible is wrong here and it could lead to suboptimal or no solutions in some cases. For ex, if coin denomination are 1, 4, 6 and we want change for 8. Using one coin of denomination 6 forces us to use 2 coins of denomination 1, but clearly the optimal solution is to use 2 coin of denomination 4 each. The key observation to make is the optimal structure of the sub-problem. If we assume for the time being that we have optimal change for all values < i. To produce change for value i, we need to add a coin to some previous solution with value j < i. We need to choose j that minimizes the value of change[i], the O(V*N) algorithm looks like the following:

change[0] = 0 // no coin required.
for i = 1 to V
  change[i] = INF
  for j = 1 to N
    if i >= C[j] and change[i] > change[i - C[j]]
      change[i] = 1 + change[i - C[j]]
return change[n]

To print the choice of coins, we can keep a separate array to track which coin, cj was chosen for a given i.

Source Code: coin_change.py