What is the algorithm for withdrawing funds from an ATM?

Question

Programming

The ATM dispenses banknotes in denominations of 1, 3, 5, 10, 25, 50, 100, 500, 1000 and 5000 rubles.
There may be a limited number of banknotes in an ATM.
The amount is received at the input and you need to give it out with these banknotes.
For example, 12. This amount can be given as one tens and two ones, two fives and two ones, or four threes.
I tried to implement a run from a larger bill to a smaller one using a greedy algorithm. As a result, it works perfectly when the banknotes are not limited.
But I can't think of what to do in this task. Tell me something?

Answer 1

understand
in general terms the problem has no solution, by the way

Answer 2

The priority of the algorithm is to try to equalize the number of remaining bills.
It is necessary to calculate the spread in the number of denominations after issuance, and choose the option after which this spread is minimal among all options. The word "scatter" means the standard deviation.
When there are no banknotes left, it is necessary to show a warning that “The ATM dispenses X and Y banknotes”, and if the requested amount is not made up by the available set, offer the nearest more and the nearest less that it can dispense.

Answer 3

well, it's easy, for example, you need to issue 1100:
there must be a structure that contains the remaining number of banknotes, for example:
ru50 = 10,
ru100 = 2,
ru500 = 1,
ru1000 = 0,
ru5000 = 1;
further: count to this amount from the largest bill immediately with a check:

// псевдокод
while( NeedGiveMoneyAmount => ru50) {
if 1000 <= NeedGiveMoneyAmount AND ru1000 > 0 then
  приготовить одну 1000ю купюру
  continue;
end if;
if 500 <= NeedGiveMoneyAmount AND ru500 > 0 then
  приготовить одну 500ю купюру
  continue;
end if;
if 100 <= NeedGiveMoneyAmount AND ru100 > 0 then
  приготовить одну 100ю купюру
  continue;
end if;
if 50 <= NeedGiveMoneyAmount AND ru50 > 0 then
  приготовить одну 50ю купюру
  continue;
end if;
}

if NeedGiveMoneyAmount > 0 // осталась сдача, нужно решить что делать дальше
elif NeedGiveMoneyAmount == 0 //выдать всё что насчитали
else // ЫЫЫЫ :DD