def greedyChange(amount, denominations):
    n = 0
    for coinValue in denominations:
        count = amount//coinValue
        amount -= count*coinValue
        print "%d x %d," % (count, coinValue),
        n += count
    print
    return n

def exhaustiveChange(amount, denominations):
    tests = 0
    bestN = 100
    count = [0 for i in xrange(len(denominations))]
    while True:
        for i, coinValue in enumerate(denominations):
            count[i] += 1
            if (count[i]*coinValue < 100):
                break
            count[i] = 0
        n = sum(count)
        if n == 0:
            break
        value = sum([count[i]*denominations[i] for i in xrange(len(denominations))])
        if (value == amount):
            if (n < bestN):
                print ", ".join(["%d x %d" % (count[i], denominations[i]) for i in xrange(len(denominations))])
                bestN = n
        tests += 1
    print tests, "Tests"
    return bestN

def branchAndBoundChange(amount, denominations):
    tests = 0
    bestN = amount
    count = [0 for i in xrange(len(denominations))]
    while True:
        for i, coinValue in enumerate(denominations):
            count[i] += 1
            if (count[i]*coinValue < amount):
                break
            count[i] = 0
        n = sum(count)
        if n == 0:
            break
        if (n > bestN):
            continue
        value = sum([count[i]*denominations[i] for i in xrange(len(denominations))])
        if (value == amount):
            if (n < bestN):
                print ", ".join(["%d x %d" % (count[i], denominations[i]) for i in xrange(len(denominations))])
                bestN = n
        tests += 1
    print tests, "Tests"
    return bestN

Count = 0

def RecursiveChange(M, c):
    global Count
    Count += 1
    if (M == 0):
        return [0 for i in xrange(len(c))]
    smallestNumberOfCoins = M+1
    for i in xrange(len(c)):
        if (M >= c[i]):
            thisChange = RecursiveChange(M - c[i], c)
            thisChange[i] += 1
            if (sum(thisChange) < smallestNumberOfCoins):
                bestChange = thisChange
                smallestNumberOfCoins = sum(thisChange)
    return bestChange

def DPChange(M, c):
    change = [[0 for i in xrange(len(c))]]
    for m in xrange(1,M+1):
        bestNumCoins = m+1
        for i in xrange(len(c)):
            if (m >= c[i]):
                thisChange = [x for x in change[m - c[i]]]
                thisChange[i] += 1
                if (sum(thisChange) < bestNumCoins):
                    change[m:m] = [thisChange]
                    bestNumCoins = sum(thisChange)
    return change[M]


if __name__ == "__main__":
    M = 42
    print greedyChange(M, (25, 20, 10, 5, 1))
    print
    print exhaustiveChange(M, (25, 20, 10, 5, 1))
    print
    print branchAndBoundChange(M, (25, 20, 10, 5, 1))
    print
    print RecursiveChange(M, (25, 20, 10, 5, 1))
    print Count
    print
    print DPChange(M, (25, 20, 10, 5, 1))