10.39

A Python Solution - O(1)

import sys
n = int(sys.argv[1])

OUT_TMP = "Min # of coins for covering %d: %d, coins used: %s"
COINS = tuple(sorted((3, 4, 9, 20, 22, 23), reverse=True))
FAILSAFE_MAX = 9999999999

if len(COINS) < 1: raise Exception("Coins please!")
if len(COINS) == 1:
    c = COINS[0]
    if n % c == 0:
        print OUT_TMP % (n, n/c, [c]*(n/c))
        sys.exit()
    else:
        raise Exception("Impossible!")

CAL_MAX = min(COINS[0] * COINS[1], n+1)

min_coins_n = [0]
min_coins_l = [()]

for i in xrange(1, CAL_MAX):
    if i in COINS:
        min_coins_n.append(1)
        min_coins_l.append((i,))
    else:
        current_min = -1
        for c in COINS:
            smaller_i = i - c
            if smaller_i > 0 and min_coins_n[smaller_i] < FAILSAFE_MAX and \
               (current_min == -1 or min_coins_n[smaller_i] < min_coins_n[current_min]):
                current_min = smaller_i

        if current_min != -1:
            min_coins_n.append(min_coins_n[current_min] + 1)
            l = list(min_coins_l[current_min]) # copy
            l.append(i - current_min)
            # another copy, not required but robuster code
            ll = tuple(l)
            min_coins_l.append(tuple(l))
        else:
            # not changable using the current coins
            min_coins_n.append(FAILSAFE_MAX)
            min_coins_l.append(None)

big_part_n = 0
coins_list = []
remaining_n = n
if n > CAL_MAX:
    n_big_part = n - CAL_MAX
    big_part_n = (n_big_part / COINS[0]) + 1
    coins_list = [COINS[0]] * big_part_n
    remaining_n -= big_part_n * COINS[0]

final_n = big_part_n + min_coins_n[remaining_n]
if final_n >= FAILSAFE_MAX:
    raise Exception("Impossible!")
coins_list.extend(min_coins_l[remaining_n])
print OUT_TMP % (n, final_n, coins_list)

A Java solution - O(n)

public class CoinProblem {

    public static void main(String[] args) {
        int sumToMakeChangeFor = 20;
        int[] coinDenominations = new int[]{1, 2, 5, 10};

        System.out.println("Number of coins needed = " + numberOfCoinsNeededForChange(sumToMakeChangeFor, coinDenominations));
    }

    private static int numberOfCoinsNeededForChange(int sum, int[] coinDenominations) {
        int[] minimumNumberOfCoinsNeeded = new int[sum + 1];
        for (int i = 0; i <= sum; i++){
            minimumNumberOfCoinsNeeded[i] = Integer.MAX_VALUE;
        }
        minimumNumberOfCoinsNeeded[0] = 0;

        for (int currentSum = 1; currentSum <= sum; currentSum++) {
            for (int j = 0; j < coinDenominations.length; j++) {
                if (coinDenominations[j] <= currentSum && 
                          ((minimumNumberOfCoinsNeeded[currentSum - coinDenominations[j]] + 1) < minimumNumberOfCoinsNeeded[currentSum]))
                    minimumNumberOfCoinsNeeded[currentSum] = minimumNumberOfCoinsNeeded[currentSum - coinDenominations[j]] + 1;
            }
        }
        return minimumNumberOfCoinsNeeded[sum];
    }
}

Reference: Dynamic Programming, TopCoder.com

Back to Chapter 10