Найдите наименьшее количество монет, которое можно изменить, от 1 до 99 центов.

Question

Недавно я попросил моего коллегу написать алгоритм для решения этой проблемы:

Найдите наименьшее количество монет, которое можно изменить, от 1 до 99 центов. Монеты могут быть только пенни (1), никели (5), десять центов (10) и четверти (25), и вы должны иметь возможность делать каждое значение от 1 до 99 (с шагом в 1 цент), используя эти монеты.

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

Мне было интересно, сможет ли кто-нибудь указать мне правильное направление или предложить более эффективный алгоритм.

Answer 1

То, что вы ищете, это Динамическое программирование .

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

Ваш алгоритм должен принимать 2 параметра:

• Список возможных значений монет, здесь [1, 5, 10, 25]
• Диапазон охвата, здесь [1, 99]

И цель состоит в том, чтобы вычислить минимальный набор монет, необходимый для этого диапазона.

Самый простой способ - действовать снизу вверх:

Range     Number of coins (in the minimal set)
          1   5   10   25
[1,1]     1
[1,2]     2
[1,3]     3
[1,4]     4
[1,5]     5
[1,5]*    4   1             * two solutions here
[1,6]     4   1
[1,9]     4   1
[1,10]    5   1             * experience tells us it's not the most viable one :p
[1,10]    4   2             * not so viable either
[1,10]    4   1   1
[1,11]    4   1   1
[1,19]    4   1   1
[1,20]    5   1   1         * not viable (in the long run)
[1,20]    4   2   1         * not viable (in the long run)
[1,20]    4   1   2

Это довольно просто, на каждом шаге мы можем продолжить, добавив не более одной монеты, нам просто нужно знать, где. Это сводится к тому, что диапазон [x,y] включен в [x,y+1], поэтому минимальный набор для [x,y+1] должен включать минимальный набор для [x,y].

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

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

Например, обратите внимание, что:

 [1,5]    4*1  1*5
 [1,9]    4*1  1*5

мы добавляем никель для покрытия [1,5], но это дает нам до [1,9] бесплатно!

Тем не менее, когда я имею дело с возмутительными наборами ввода [2,3,5,10,25] для покрытия [2,99], я не уверен, как быстро проверить диапазон, охватываемый новым набором, иначе это будет более эффективно.

Answer 2

Вы можете очень быстро найти верхнюю границу.

Скажем, вы берете три четверти. Тогда вам нужно будет только заполнить «пробелы» 1-24, 26-49, 51-74, 76-99 другими монетами.

Тривиально, это будет работать с 2 центами, 1 никелем и 4 копейками.

Таким образом, 3 + 4 + 2 + 1 должно быть верхней границей для вашего количества монет. Всякий раз, когда ваш алгоритм перебора оказывается выше thta, вы можете немедленно прекратить поиск еще глубже.

Остальная часть поиска должна выполняться достаточно быстро для любых целей с динамическим программированием.

(правка: фиксированный ответ согласно наблюдению Гейба)

Answer 3

Вам нужно как минимум 4 копейки, так как вы хотите получить 4 в качестве сдачи, и вы можете сделать это только с копейками.

Неоптимально иметь более 4 копеек.Вместо 4 + х копеек у вас может быть 4 копейки и х никелей - они охватывают как минимум один и тот же диапазон.

Таким образом, у вас есть ровно 4 копейки.

Вам нужен как минимум 1 никель,так как вы хотите получить 5 в качестве замены.

Не оптимально иметь более 1 никеля.Вместо 1 + x никелей вы можете иметь 1 никель и x центов - они охватывают как минимум один и тот же диапазон.

Таким образом, у вас есть ровно 1 никель.

Вам нужно минимум 2 цента,так как вы хотите получить 20.

Это означает, что у вас есть 4 копейки, 1 никель и минимум 2 цента.

Если бы у вас было менее 10 монет, у вас было бы менее 3 четвертей.Но тогда максимально возможное изменение, которое вы можете получить, используя все монеты, 4 + 5 + 20 + 50 = 79, недостаточно.

Это означает, что у вас есть как минимум 10 монет. Ответ Томаса показывает, что на самом деле, если у вас есть 4 копейки, 1 никель, 2 цента и 3 четверти, все хорошо.

Answer 4

Сегодня я узнал о динамическом программировании , и вот результат:

coins = [1,5,10,25]
d = {} # stores tuples of the form (# of coins, [coin list])

# finds the minimum # of coins needed to
# make change for some number of cents
def m(cents):
    if cents in d.keys():
        return d[cents]
    elif cents > 0:
        choices = [(m(cents - x)[0] + 1, m(cents - x)[1] + [x]) for x in coins if cents >= x]

        # given a list of tuples, python's min function
        # uses the first element of each tuple for comparison
        d[cents] = min(choices)
        return d[cents]
    else:
        d[0] = (0, [])
        return d[0]

for x in range(1, 100):
    val = m(x)
    print x, "cents requires", val[0], "coins:", val[1]

Динамическое программирование действительно волшебно.

Answer 5

Хороший вопрос. Это логика, которую я придумал. Протестировано с несколькими сценариями, включая 25.

class Program
{

    //Allowable denominations
    const int penny = 1;
    const int nickel = 5;
    const int dime = 10;
    const int quarter = 25;

    const int maxCurrencyLevelForTest =55; //1-n where n<=99

    static void Main(string[] args)
    {         
        int minPenniesNeeded = 0;
        int minNickelsNeeded = 0; 
        int minDimesNeeded = 0; 
        int minQuartersNeeded = 0;


        if (maxCurrencyLevelForTest == penny)
        {
            minPenniesNeeded = 1;
        }
        else if (maxCurrencyLevelForTest < nickel)
        {
            minPenniesNeeded = MinCountNeeded(penny, maxCurrencyLevelForTest);                
        }
        else if (maxCurrencyLevelForTest < dime)
        {
            minPenniesNeeded = MinCountNeeded(penny, nickel - 1);
            minNickelsNeeded = MinCountNeeded(nickel, maxCurrencyLevelForTest);                
        }
        else if (maxCurrencyLevelForTest < quarter)
        {
            minPenniesNeeded = MinCountNeeded(penny, nickel - 1);
            minNickelsNeeded = MinCountNeeded(nickel, dime - 1);
            minDimesNeeded = MinCountNeeded(dime, maxCurrencyLevelForTest);
        }
        else
        {
            minPenniesNeeded = MinCountNeeded(penny, nickel - 1);
            minNickelsNeeded = MinCountNeeded(nickel, dime - 1);
            minDimesNeeded = MinCountNeeded(dime, quarter - 1);

            var maxPossilbleValueWithoutQuarters = (minPenniesNeeded * penny + minNickelsNeeded * nickel + minDimesNeeded * dime);
            if (maxCurrencyLevelForTest > maxPossilbleValueWithoutQuarters)
            {               
                minQuartersNeeded = (((maxCurrencyLevelForTest - maxPossilbleValueWithoutQuarters)-1) / quarter) + 1;
            }
        }


        var minCoinsNeeded = minPenniesNeeded + minNickelsNeeded+minDimesNeeded+minQuartersNeeded;

        Console.WriteLine(String.Format("Min Number of coins needed: {0}", minCoinsNeeded));
        Console.WriteLine(String.Format("Penny: {0} needed", minPenniesNeeded));
        Console.WriteLine(String.Format("Nickels: {0} needed", minNickelsNeeded));
        Console.WriteLine(String.Format("Dimes: {0} needed", minDimesNeeded));
        Console.WriteLine(String.Format("Quarters: {0} needed", minQuartersNeeded));
        Console.ReadLine();
    }

    private static int MinCountNeeded(int denomination, int upperRange)
    {
        int remainder;
        return System.Math.DivRem(upperRange, denomination,out remainder);
    }
}

Некоторые результаты: Когда maxCurrencyLevelForTest = 25

Min Number of coins needed: 7
Penny: 4 needed
Nickels: 1 needed
Dimes: 2 needed
Quarters: 0 needed

Когда maxCurrencyLevelForTest = 99

Min Number of coins needed: 10
Penny: 4 needed
Nickels: 1 needed
Dimes: 2 needed
Quarters: 3 needed

maxCurrencyLevelForTest: 54

Min Number of coins needed: 8
Penny: 4 needed
Nickels: 1 needed
Dimes: 2 needed
Quarters: 1 needed

maxCurrencyLevelForTest: 55

Min Number of coins needed: 9
Penny: 4 needed
Nickels: 1 needed
Dimes: 2 needed
Quarters: 2 needed

maxCurrencyLevelForTest: 79

Min Number of coins needed: 9
Penny: 4 needed
Nickels: 1 needed
Dimes: 2 needed
Quarters: 2 needed

maxCurrencyLevelForTest: 85

Min Number of coins needed: 10
Penny: 4 needed
Nickels: 1 needed
Dimes: 2 needed
Quarters: 3 needed

Я думаю, код может быть подвергнут рефакторингу.

Answer 6

Редактировать: Как отметили комментаторы, я неверно истолковал вопрос.(Вопрос очень похож на основную проблему CS, я вижу, что студентам колледжа приходится решать ...) машет рукой Это не тот ответ, который вы ищете.Тем не менее, хотя первоначальный ответ неверен, мы можем использовать его в качестве ступеньки к решению O ( n ).

Итак, примите неправильный ответ ниже, который решает только дляодно значение (т. е. минимальный размер чеканки, необходимый для 68 центов) и просто запустите его для каждого значения.

changes = []
for amount in xrange(1, 100): # [1, 99]
    changes.append( run_the_algo_below( amount ) )
# Take the maximum for each coin type.
# ie, if run_the_algo_below returns (q, d, n, p):
change = [0, 0, 0, 0]
for c in changes:
    change = [max(c[i], change[i] for i in xrange(0, 4)]

Теперь это, безусловно, даст вам правильный ответ, но является ли он минимальным ответом?(это самая сложная часть. В настоящее время моя интуиция говорит да, но я все еще думаю об этом ...)

---

( Неправильный ответ )

Ничего себе.Loops?Динамическое программирование?Неужели люди?

В Python:

amount = ( your_amount_in_cents )

quarters = amount // 25
dimes = amount % 25 // 10
nickels = amount % 25 % 10 // 5
pennies = amount % 25 % 10 % 5

Возможно, некоторые из этих операций по модулю можно упростить ...

Это не сложно, вам просто нужно подуматьо том, как вы делаете изменения в реальной жизни.Вы выдаете кварталы до тех пор, пока добавление еще одной четверти не поставит вас на желаемую сумму, вы начисляете десять центов, пока добавление еще одного цента не приведет к превышению желаемой суммы, и так далее.Затем преобразуйте в математические операции: по модулю и делению.То же самое решение применяется к долларам, переводя секунды в ЧЧ: ММ: СС и т. Д.

Answer 7

После неудачного поиска хорошего решения проблемы такого типа в PHP, я разработал эту функцию.

Он берет любую сумму денег (до $ 999,99) и возвращает массив минимального количества каждого купюры / монеты, необходимого для получения этого значения.

Сначала он преобразует значение вint в пенни (по какой-то причине я получал бы ошибки в самом конце при использовании стандартных значений float).

Возвращенные купюры также указаны в копейках (то есть: 5000 = 50 долларов, 100 = 1 доллар и т. Д.).

function makeChange($val)
{
    $amountOfMoney = intval($val*100);
    $cashInPennies = array(10000,5000,2000,1000,500,100,25,10,5,1);
    $outputArray = array();
    $currentSum = 0;
    $currentDenom = 0;

    while ($currentSum < $amountOfMoney) {
        if( ( $currentSum + $cashInPennies[$currentDenom] ) <= $amountOfMoney  ) {
            $currentSum = $currentSum + $cashInPennies[$currentDenom];
            $outputArray[$cashInPennies[$currentDenom]]++;
        } else {
            $currentDenom++;
        }
    }

    return $outputArray;

}

$change = 56.93;
$output = makeChange($change);

print_r($output);
echo "<br>Total number of bills & coins: ".array_sum($output);

=== OUTPUT ===

Array ( [5000] => 1 [500] => 1 [100] => 1 [25] => 3 [10] => 1 [5] => 1 [1] => 3 ) 
Total number of bills & coins: 11

Answer 8

Предполагая, что вы говорите о валюте США, вам нужен алгоритм жадности: http://en.wikipedia.org/wiki/Greedy_algorithm

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

Для общего случая см. http://en.wikipedia.org/wiki/Change-making_problem,, потому что вы хотели бы использовать динамическое программирование или линейное программирование, чтобы найти ответ для произвольных номиналов, где жадный алгоритм не 'т работа.

Answer 9

Это может быть общим решением в C #

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace CoinProblem
{
    class Program
    {
        static void Main(string[] args)
        {
            var coins = new int[] { 1, 5, 10, 25 }; // sorted lowest to highest
            int upperBound = 99;
            int numCoinsRequired = upperBound / coins.Last();
            for (int i = coins.Length - 1; i > 0; --i)
            {
                numCoinsRequired += coins[i] / coins[i - 1] - (coins[i] % coins[i - 1] == 0 ? 1 : 0);
            }
            Console.WriteLine(numCoinsRequired);
            Console.ReadLine();
        }
    }
}

Я не до конца продумал это ... слишком поздно ночью.Я думал, что ответ должен быть 9 в этом случае, но Гейб сказал, что это должно быть 10 ... что и дает.Я думаю, это зависит от того, как вы интерпретируете вопрос ... ищем ли мы наименьшее количество монет, которые могут дать любое значение <= X, или наименьшее количество монет, которые могут дать любое значение <= X, используя наименьшее количество монет?Например ... Я почти уверен, что мы можем сделать любую ценность только с 9 монетами, без никелей, но затем, чтобы произвести 9 ... вам нужно ... ох ... Понятно.Вам понадобится 9 копеек, которых у вас нет, потому что это не то, что мы выбрали ... в <em>случае , я думаю, этот ответ правильный.Просто рекурсивная реализация идеи Томаса, но я не знаю, почему он остановился там ... вам не нужно ничего грубо насиловать.

Редактировать: Это будет неправильно.

Answer 10

Задание

Find the least number of coins required, that can make any change from 1 to 99 cent.

отличается от задачи

For each single change from 1 to 99 cent, find the least number of coins required.

потому что решение может быть совершенно другим мультимножеством монет.

Предположим, у вас нет (1), (5), (10) и (25) центовых монет, но (1), (3), (5) и (17) центовые монеты: чтобы внести изменения на 5, вам нужна только одна (5) монета; но для всех изменений от 1 до 5 вам понадобятся две (1) монеты и одна (3) монета, а не любая (5) монета.

Жадный алгоритм выполняет итерацию от наименьшего значения к наибольшему в отношении значений изменений и значений монет:

With 1x(1) you get all change values below 2.

To make a change of 2, you need an additional coin,
which could have any value up to 2;
choose greedy -> choose the largest -> (1).

With 2x(1) you get all change values below 3.

To make a change of 3, you need an additional coin,
which could have any value up to 3;
choose greedy -> choose the largest -> (3).

With 2x(1)+1x(3) you get all change values below 6.

To make a change of 6, you need an additional coin,
which could have any value up to 6;
choose greedy -> choose the largest -> (5).

and so on...

То есть в Хаскеле:

coinsforchange [1,3,5,17] 99
where
    coinsforchange coins change = 
        let f (coinssofar::[Int],sumsofar::Int) (largestcoin::Int,wanttogoto::Int) = 
                let coincount=(max 0 (wanttogoto-sumsofar+largestcoin-1))`div`largestcoin
                 in (replicate coincount largestcoin++coinssofar,sumsofar+coincount*largestcoin)
         in foldl f ([],0) $ zip coins $ tail [c-1|c<-coins] ++ [change]

А в C ++:

void f(std::map<unsigned,int> &coinssofar,int &sumsofar, unsigned largestcoin, int wanttogoto)
{
    int x = wanttogoto - sumsofar + largestcoin - 1;
    coinssofar[largestcoin] = (x>0) ? (x / largestcoin) : 0;
    //returns coinssofar and sumsofar;
}
std::map<unsigned,int> coinsforchange(const std::list<unsigned> &coins, int change)
{
    std::map<unsigned,int> coinssofar;
    int sumsofar=0;
    std::list<unsigned>::const_iterator coin = coins.begin();
    unsigned largestcoin = *coin;
    for( ++coin ; coin!=coins.end() ; largestcoin=*(coin++))
        f(coinssofar,sumsofar,largestcoin,(*coin) - 1);
    f(coinssofar,sumsofar,largestcoin,change);
    return coinssofar;
}