#!/usr/local/bin/python3
# Author: Dr. Robert Heckendorn, Computer Science Department, University of Idaho, 2013
from lib import *

# for coins in positions 0..len(coins)-1
# assume coins in increasing order and coins[0] = 1
# f(i) is the minimum number of coins that adds to i
def change(coins, n) :
#    print(coins)
    f = array(n+1, None)
    b = array(n+1, None)  # for backtracking information
    f[0] = 0

    # for up to the amount you want to make change for
    for i in range(1, n+1) :
        tmp = None   # possible number of coins
        j = 0
        # try each type of coin that is legal to use here
        coin = None
        while j<len(coins) and i>=coins[j] :
            if tmp==None or f[i-coins[j]]<tmp :
                tmp = f[i-coins[j]]
                coin = j     # record the decision
            j+=1
        f[i] = tmp + 1
        b[i] = coin    # save the best choice in the backtrack array
#    print(f)
#    print(b)

    # decode the backtrack array
    ans = []
    while n>0 :
        coin = b[n]
        ans.append(coins[coin])
        n -= coins[coin]
    return ans

for n in range(1, 50) :
#    print(n, change([1, 2, 10, 20, 100], n))
    print(n, change([1, 10, 25], n))

#change([1, 2, 5, 10], 28)
#change([1, 2, 5, 10, 20, 50, 100], 188)