How to write an algorithm for selecting coins from a drawer in Python?

Question

Algorithms

There is a box in which there is a certain number of coins of different denominations. Checkout type. We know all the coins and their denominations.
You need a script to which you enter a certain amount that you need, and the script itself (preferably rationally) selects coins to issue such an amount. For example, I enter that I need $5, and the script picks up coins from the ones in the box to give me $5. Selects coins 3 coins: $4, $0.8 and $0.2.

How can this be done?

Answer 1

This is the task of changing coins. Solved by dynamic programming. Here is the wiki article . There's even code there, it seems, in python. True, it only counts the number of coins there. To find the coins themselves, you need to create another two-dimensional array and mremember where the array is considered, and by what action the current value is typed (either take the current coin, or skip it). At the end, you will need to m[-1][-1]perform the previously recorded actions from the position with a while loop (either skip the current coin and decrease r by 1, or take it and then decrease r by its size).