Алгоритм наименьшего количества изменений

Question

Да, я знаю, что подобные посты были похожи на это, однако, просматривая их все, я все еще застрял, поскольку я очень плохо знаком с программированием, и ни один из приведенных ответов не был достаточно конкретным для моей проблемы, чтобы помочь.

---

вопрос. Напишите эффективный алгоритм ACL (алгоритмический компьютерный язык), который, учитывая стоимость предмета (меньше или равный одному доллару), дает количество монет 50 центов, 20 центов, 10 центов, 5 центов и 1 цент, которые покупатель получит получить, если они сдали один доллар. Вы должны минимизировать количество монет в обмене.

---

Вопрос не относится к какому-либо конкретному языку программирования, и для ответа можно использовать только простой язык ACL, например if, if-else, while и не может использовать массивы или другие расширенные команды.

Вот где я нахожусь:

введите здесь код Алгоритм минимальной суммы изменения

{
    int cost, fifty, twenty, ten, five, one;

    fifty = 0;
    twenty = 0;
    ten = 0;
    five = 0;
    one = 0;

    read (cost);
    if (cost <= 50)
    {
        fifty = 1;

---

Готовый код, спасибо за помощь! Если вы видите какие-либо неясности или можете помочь мне упростить код, пожалуйста, дайте мне знать.

---

Algorithm how much change
{
    int cost, change, fifty, twenty, ten, five, one;

    fifty = 0;
    twenty = 0;
    ten = 0;
    five = 0;
    one = 0;

    read (cost);
    change = 100 - cost;

    if (change >= 50)
    {
        fifty = fifty + 1;
        change = change - 50;
    }
    while (change >= 20)
    {
        twenty = twenty + 1;
        change = change - 20;
    }
    while (change >= 10)
    {
        ten = ten + 1;
        change = change - 10;
    }
    while (change >= 5)
    {
        five = five + 1;
        change = change - 5;
    }
    while (change >= 1)
    {
        one = one + 1;
        change = change - 1;
    }

    print(one, five, ten, twenty, fifty);
}

Answer 1

Для ваших конкретных сумм изменений, я полагаю, сработает простая жадная наивная стратегия "выбери самую большую, пока я больше не смогу".

пример:

1. Сколько50-х можно выбрать до того, как 50-е больше, чем сумма изменения?Следите за этим числом 50, вычтите это количество из общего числа
2. Повторите для 20, 10 и т. Д.

Однако не всегда следует, что жадный метод будет работать,Для «общего» решения см. Замена монет - Алгоритмист

Answer 2

на самом деле, стоимость> = 50 нужно проверять только один раз, но это более общий вариант (для случаев свыше 1 доллара)

while (cost >= 50)
{
fifty++;
cost -= 50;
}
while (cost >= 20)
{
twenty++;
cost -=20;
}
...

Answer 3

Подсказка: начните с самой большой монеты и выясните максимальное количество монет, которые вы можете использовать, затем перейдите ко второй по величине монете и повторите.Похоже, они упростили вам использование двадцати монет вместо 25 лол.

Answer 4

Поскольку это звучит как домашнее задание, я не собираюсь сразу давать ответ, но дам вам подсказку в правильном направлении.

Допустим, вы какой-то пункт в вашей программе. Вам осталось вернуть определенную сумму, скажем, 80 центов. Как бы вы получили монету, которую вы, безусловно, должны вернуть?

Answer 5

more detailed:

and even a brute force algorithm which is O(d M^d)

This is from Макс Алексеев , University of South Carolina cse.