Какой есть алгоритм вывода средств с банкомата?

Question

[Чик-чирик]

Банкомат выдает купюры номиналом 1, 3, 5, 10, 25, 50, 100, 500, 1000 и 5000 рублей.
Купюр в банкомате может быть ограниченное количество.
На вход поступает сумма и нужно её выдать этими купюрами.

Например 12. Эта сумма может быть выдана как одна десятка и две единички, две пятерки и две единички, либо четыре тройки.

Я попытался реализовать прогон от большей купюры к меньшей с помощью жадного алгоритма. В итоге идеально работает при варианте, когда купюры не ограничены.
Но что делать в данной задаче не придумаю. Подскажите что-нибудь?

Comments

[Андрей]

Не забывайте, что банкомат может за одну операцию выдать не больше 40 банкнот.

Answer 1

[Dimonchik]

разбирайся

в общем виде задача решения не имеет, кстати

Answer 2

[Сергей Соколов]

Приоритет алгоритма – стараться выровнять кол-во остающихся купюр.

Надо посчитать разброс количеств номиналов после выдачи, и выбрать вариант, после которого этот разброс минимален среди всех вариантов. Под словом «разброс» понимать среднее квадратичное отклонение.

Когда каких-то купюр не осталось, надо показывать предупреждение, что «Банкомат выдаёт купюры достоинством X и Y», и если запрошенная сумма не составляется имеющимся набором, предлагать ближайшую больше, и ближайшую меньше, которые выдать может.

Comments

[Schullz]

А зачем Вы придумали автору дополнительные условия задачи?

[Сергей Соколов]

Schullz: «я так вижу».

Answer 3

[Kocmoc]

ну это же легко, например надо выдать 1100:
должна быть структурка которая содержит оставшееся количество купюр, например:
ru50 = 10,
ru100 = 2,
ru500 = 1,
ru1000 = 0,
ru5000 = 1;
далее: считаете к этой сумме от наибольшей купюры сразу с проверкой:

// псевдокод
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

Comments

[Schullz]

Контрпример:
нужно получить 12 рублей, у нас остались только 10рублёвые и 3рублёвые купюры (у автора в условии 3рублёвые купюры есть)
Ваш алгоритм выдаст 10 рублей, хотя можно выдать всю сумму 3рублёвыми купюрами

[Kocmoc]

я написал абстрактный код - просто пример, естественно там нужно учитывать все купюру которые есть (просто кода много получилось бы), а так да нужно учитывать все купюры как у автора: 1, 3, 5, 10, 25, 50, 100, 500, 1000 и 5000 рублей.

[Чик-чирик]

Koc: ну так суть в том, что по вашему алгоритму мы найдем эту десятку и надо будет выдать еще 2 рубля, которые мы дать не сможем (так как нет рублевых купюр в наличии). программа скажет "нечем выплатить", а на деле мы бы могли выплатить 4 штуки по 3 рубля. вы описали методику жадного алгоритма. он хорош, если купюры у нас не ограничены.