from numpy import minimum


INF = 999999

def coins_changing(v,coin_list):
    """
    int v: given value to exchange with coins
    list coin_list: a sequence of coin values, like 1p,2p,5p...
    
    return the number of coins 
    """
    k = len(coin_list)     # number of denominations of the coin 
    C = [INF] * (v + 1)    # minimum number of coins needed to make the change 
    P = [INF] * (v + 1)    # extra array P to store the "coin used to get the best answer"
    
    C[0] = 0
    C[1] = 1
    
    for i in range(2,v+1):
        for j in range(1,k):
            if (i >= coin_list[j] and C[i] > 1 + C[i-coin_list[j]]):
                C[i] = 1 + C[i-coin_list[j]]
                P[i] = j
                
    while v > 0:
        j = P[v]
        v = v - coin_list[j]
        
    return C[v]

def coins_changing1(d, n, k):
    M = [0]*(n+1)
    S = [0]*(n+1)

    for j in range(1, n+1):
        minimum = INF
        coin = 0

        for i in range(1, k+1):
            if(j >= d[i]):
                minimum = min(minimum, 1+M[j-d[i]])
                coin = i
        M[j] = minimum
        S[j] = coin

    l = n
    while(l>0):
        print(d[S[l]])
        l = l-d[S[l]]
    return M[n]
    
    
if __name__ == '__main__':
    Coins = [0, 1, 5, 10]
    print(coins_changing1(Coins,12,3))
        
    
    
    
    