Answer to Question #94101 in Algorithms for Catherine enri

Question #94101
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)
1
Expert's answer
2019-09-10T05:46:30-0400
# 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()

Need a fast expert's response?

Submit order

and get a quick answer at the best price

for any assignment or question with DETAILED EXPLANATIONS!

Comments

No comments. Be the first!

Leave a comment

LATEST TUTORIALS
New on Blog
APPROVED BY CLIENTS