Answer to Question #94101 in Algorithms for Catherine enri

Question

A person enters the bank and stand in the queue to get his salary. When his turn comes, he request the cashier that i need my salary with minimum notes and coins. Write the program for the cashier that first ask the cashier to enter the salary amount and then display the number of notes and coins of (rs. 5000, rs 1000, rs 100, rs 50, rs 20, rs 10, rs 5, rs 2, rs 1)

Answer 1

# Reference:
# runestone.academy/runestone/books/published/pythonds/Recursion/DynamicProgramming.html

def solve(money, amount, counts, answer):
    for value in range(amount + 1):
        count = value  # 1 must be the smallest face value in money
        last = 1
        for j in money:
            if j > value:  # money must be sorted
                break
            if counts[value - j] + 1 < count:
                count = counts[value-j] + 1
                last = j
        counts[value] = count
        answer[value] = last
    return counts[amount]


def display(amount, counts, answer):
    last = amount
    values = []
    while last != 0:
        values.append(answer[last])
        last -= answer[last]
    unique = sorted(set(values))
    print('count: {} ({})'.format(counts[amount], len(unique)))
    print('values:')
    for x in unique:
        print('  {} x {}'.format(x, values.count(x)))


def main():
    amount = 6789
    money = sorted([5000, 1000, 100, 50, 20, 10, 5, 2, 1])
    counts = [0] * (amount + 1)
    answer = counts[:]

    solve(money, amount, counts, answer)
    display(amount, counts, answer)


if __name__ == '__main__':
    main()