Алгоритм выдачи сдачи

Есть необходимость разработать алгоритм выдачи сдачи монетами. Погуглил и в большей степени наткнулся на варианты так называемого жадного алгоритма. Сначала выдаём наибольшим номиналом и затем по оставшейся сумме идём вниз. Но этот алгоритм сломается допустим о следующий пример. В автомате есть 3 номинала в рублях: 5 2 1

Мне нужно выдать сдачу в 6 рублей. Соответственно по жадному алгоритму нужно бы выдать 5 и 1. Но допустим что в автомате есть одна 5 рублёвая монета и три 2 рублёвых, а рублей нет. А я уже в алгоритме приплюсую пятёрку и как тогда быть в таком случае? Как по алгоритму возвращаться назад и пересчитывать?