Как составить алгоритм выбора монет из ящика на Python?

Question

[tmkbl]

Есть ящик, в котором есть какое-то количество монет разных номиналов. Типа кассы. Все монеты и их номиналы мы знаем.
Нужен скрипт, которому вводишь определенную сумму, которая тебе нужна, и скрипт сам (желательно рационально) подбирает монеты для выдачи такой суммы. Например, я ввожу, что мне нужно 5$, и скрипт подбирает монеты из имеющихся в ящике, чтобы выдать мне 5$. Выбирает монеты 3 монеты: 4$, 0,8$ и 0,2$.

Как такое можно сделать?

Comments

[Vindicar]

Дьявол, как всегда, в деталях. Что такое "рационально"?
Наименьшее количество монет?
Наименьшее количество типов момент?
По возможности сохранять пропорцию разных монет в ящике, для обслуживания других клиентов?
Всё сразу?

Answer 1

[Wataru]

Это задача размена монет. Решается динамическим программированием. Вот статья на вики. Там даже код есть, похоже, на питоне. Правда, оно там только количество монет считает. Чтобы найти и сами монеты, вам надо завести еще один двумерный массив и везде, где считается массив m запоминать, а каким именно действием текущее значение набирается (или взять текущую монету, или пропустить). В конце вам надо будет от позиции m[-1][-1] циклом while выполнять записанные ранее действия (или пропустить текущую монету и уменьшить r на 1, или взять и тогда уменьшить r на ее размер).