Найдите наименьшее количество монет, которые могут внести любое изменение от 1 до 99 центов

Ответ 1

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

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

Вам необходимо выполнить два параметра:

• Список возможных значений монет, здесь [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 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], я не уверен, как быстро проверить диапазон, охваченный новым набором, или это будет фактически более эффективно.

Ответ 2

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

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

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

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

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

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

Ответ 3

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

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

Итак, у вас ровно 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 четверти, все хорошо.

Ответ 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 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]

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

Ответ 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

Код может быть реорганизован, я думаю.

Ответ 6

Изменить: Как отмечали комментаторы, я неправильно истолковал этот вопрос. (Вопрос очень похож на базовую проблему CS, которую я вижу, когда учащиеся в колледже должны решить...) wave hand Это не тот ответ, который вы ищете. Тем не менее, хотя первоначальный ответ неверен, мы можем использовать его в качестве шага к решению 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

Возможно, некоторые из этих операций modulo могут быть упрощены...

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

Ответ 7

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

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

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

Ответ 8

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

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

Сначала он преобразует значение в int в pennies (по какой-то причине я получал ошибки в самом конце при использовании стандартных значений 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

Ответ 9

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

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 пенни, которых у вас нет, потому что это не то, что мы выбрали... в этом случае, я думаю, этот ответ прав. Рекурсивная реализация идеи Томаса, но я не знаю, почему он остановился там. Вам не нужно ничего перебирать.

Изменить: Это неверно.

Ответ 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...

Это в Haskell:

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]

И в С++:

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;
}

Ответ 11

В общем, если у вас есть ваши монеты COIN [] и ваш "диапазон изменения" 1..MAX, следующее должно найти максимальное количество монет.

Initialise array CHANGEVAL[MAX] to -1

For each element coin in COIN:
  set CHANGEVAL[coin] to 1
Until there are no more -1 in CHANGEVAL:
  For each index I over CHANGEVAL:
    if CHANGEVAL[I] != -1:
      let coincount = CHANGEVAL[I]
      For each element coin in COIN:
        let sum = coin + I
        if (COINS[sum]=-1) OR ((coincount+1)<COINS[sum]):
          COINS[sum]=coincount+1

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

Ответ 12

Версия vb

Public Class Form1

    Private Sub Button1_Click(ByVal sender As System.Object, _
                              ByVal e As System.EventArgs) Handles Button1.Click
        For saleAMT As Decimal = 0.01D To 0.99D Step 0.01D
            Dim foo As New CashDrawer(0, 0, 0)
            Dim chg As List(Of Money) = foo.MakeChange(saleAMT, 1D)
            Dim t As Decimal = 1 - saleAMT
            Debug.WriteLine(t.ToString("C2"))
            For Each c As Money In chg
                Debug.WriteLine(String.Format("{0} of {1}", c.Count.ToString("N0"), c.moneyValue.ToString("C2")))
            Next
        Next
    End Sub

    Class CashDrawer

        Private _drawer As List(Of Money)

        Public Sub New(Optional ByVal QTYtwoD As Integer = -1, _
                       Optional ByVal QTYoneD As Integer = -1, _
                       Optional ByVal QTYfifty As Integer = -1, _
                       Optional ByVal QTYquarters As Integer = -1, _
                       Optional ByVal QTYdimes As Integer = -1, _
                       Optional ByVal QTYnickels As Integer = -1, _
                       Optional ByVal QTYpennies As Integer = -1)
            _drawer = New List(Of Money)
            _drawer.Add(New Money(2D, QTYtwoD))
            _drawer.Add(New Money(1D, QTYoneD))
            _drawer.Add(New Money(0.5D, QTYfifty))
            _drawer.Add(New Money(0.25D, QTYquarters))
            _drawer.Add(New Money(0.1D, QTYdimes))
            _drawer.Add(New Money(0.05D, QTYnickels))
            _drawer.Add(New Money(0.01D, QTYpennies))
        End Sub

        Public Function MakeChange(ByVal SaleAmt As Decimal, _
                                   ByVal amountTendered As Decimal) As List(Of Money)
            Dim change As Decimal = amountTendered - SaleAmt
            Dim rv As New List(Of Money)
            For Each c As Money In Me._drawer
                change -= (c.NumberOf(change) * c.moneyValue)
                If c.Count > 0 Then
                    rv.Add(c)
                End If
            Next
            If change <> 0D Then Throw New ArithmeticException
            Return rv
        End Function
    End Class

    Class Money
        '-1 equals unlimited qty
        Private _qty As Decimal 'quantity in drawer
        Private _value As Decimal 'value money
        Private _count As Decimal = 0D

        Public Sub New(ByVal theValue As Decimal, _
                       ByVal theQTY As Decimal)
            Me._value = theValue
            Me._qty = theQTY
        End Sub

        ReadOnly Property moneyValue As Decimal
            Get
                Return Me._value
            End Get
        End Property

        Public Function NumberOf(ByVal theAmount As Decimal) As Decimal
            If (Me._qty > 0 OrElse Me._qty = -1) AndAlso Me._value <= theAmount Then
                Dim ct As Decimal = Math.Floor(theAmount / Me._value)
                If Me._qty <> -1D Then 'qty?
                    'limited qty
                    If ct > Me._qty Then 'enough 
                        'no
                        Me._count = Me._qty
                        Me._qty = 0D
                    Else
                        'yes
                        Me._count = ct
                        Me._qty -= ct
                    End If
                Else
                    'unlimited qty
                    Me._count = ct
                End If
            End If
            Return Me._count
        End Function

        ReadOnly Property Count As Decimal
            Get
                Return Me._count
            End Get
        End Property
    End Class
End Class

Ответ 13

Вот простая версия в Python.

#!/usr/bin/env python

required = []
coins = [25, 10, 5, 1]

t = []
for i in range(1, 100):
    while sum(t) != i:
        for c in coins:
            if sum(t) + c <= i:
                t.append(c)
                break
    for c in coins:
        while t.count(c) > required.count(c):
            required.append(c)
    del t[:]

print required

При запуске он выводит следующее на стандартный вывод.

[1, 1, 1, 1, 5, 10, 10, 25, 25, 25]

Код довольно понятен (спасибо Python!), но в основном алгоритм состоит в том, чтобы добавить самую большую доступную монету, которая не помещает вас в текущую сумму, которую вы снимаете, в свой временный список монет (t в этом случае). Как только вы найдете наиболее эффективный набор монет для определенной суммы, убедитесь, что в требуемом списке есть по крайней мере одна часть каждой монеты. Сделайте это за каждый итог от 1 до 99 центов, и все готово.

Ответ 14

Я написал этот алгоритм для аналогичной проблемы с DP, может ли он помочь

public class MinimumCoinProblem {

    private static void calculateMinumCoins(int[] array_Coins, int sum) {

        int[] array_best = new int[sum];

        for (int i = 0; i < sum; i++) {
            for (int j = 0; j < array_Coins.length; j++) {
                    if (array_Coins[j] <= i  && (array_best[i] == 0 || (array_best[i - array_Coins[j]] + 1) <= array_best[i])) {
                        array_best[i] = array_best[i - array_Coins[j]] + 1;
                    }
            }
        }
        System.err.println("The Value is" + array_best[14]);

    }


    public static void main(String[] args) {
        int[] sequence1 = {11, 9,1, 3, 5,2 ,20};
        int sum = 30;
        calculateMinumCoins(sequence1, sum);
    }

}

Ответ 15

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

def min_any_change():
    V, C = [1, 5, 10, 25], 99
    mxP, mxN, mxD, mxQ = 0, 0, 0, 0
    solution = min_change_table(V, C)
    for i in xrange(1, C+1):
        cP, cN, cD, cQ = 0, 0, 0, 0
        while i:
            coin = V[solution[i]]
            if coin == 1:
                cP += 1
            elif coin == 5:
                cN += 1
            elif coin == 10:
                cD += 1
            else:
                cQ += 1
            i -= coin
        if cP > mxP:
            mxP = cP
        if cN > mxN:
            mxN = cN
        if cD > mxD:
            mxD = cD
        if cQ > mxQ:
            mxQ = cQ
    return {'pennies':mxP, 'nickels':mxN, 'dimes':mxD, 'quarters':mxQ}

def min_change_table(V, C):
    m, n, minIdx = C+1, len(V), 0
    table, solution = [0] * m, [0] * m
    for i in xrange(1, m):
        minNum = float('inf')
        for j in xrange(n):
            if V[j] <= i and 1 + table[i - V[j]] < minNum:
                minNum = 1 + table[i - V[j]]
                minIdx = j
        table[i] = minNum
        solution[i] = minIdx
    return solution

Выполнение min_any_change() дает ответ, который мы искали: {'pennies': 4, 'nickels': 1, 'dimes': 2, 'quarters': 3}. В качестве теста мы можем попытаться удалить монету любого достоинства и проверить, возможно ли еще произвести изменение для любой суммы в диапазоне 1..99:

from itertools import combinations

def test(lst):
    sums = all_sums(lst)
    return all(i in sums for i in xrange(1, 100))

def all_sums(lst):
    combs = []
    for i in xrange(len(lst)+1):
        combs += combinations(lst, i)
    return set(sum(s) for s in combs)

Если мы проверим результат, полученный выше, получим a True:

test([1, 1, 1, 1, 5, 10, 10, 25, 25, 25])

Но если мы удалим одну монету, независимо от того, какую деноминацию, мы получим False:

test([1, 1, 1, 5, 10, 10, 25, 25, 25])

Ответ 16

С одной стороны, на это был дан ответ. С другой стороны, для большинства ответов требуется много строк кода. Этот ответ Python не требует много строк кода, а всего лишь много строк мысли ^ _ ^:

div_round_up = lambda a, b: a // b if a % b == 0 else a // b + 1

def optimum_change(*coins):
    wallet = [0 for i in range(0, len(coins) - 1)]
    for j in range(0, len(wallet)):
        target = coins[j + 1] - 1 
        target -= sum(wallet[i] * coins[i] for i in range(0, j))
        wallet[j] = max(0, div_round_up(target, coins[j]))
    return wallet

optimum_change(1, 5, 10, 25, 100)
#  [4, 1, 2, 3]

Это очень простой алгоритм масштабирования, который может сломаться для входов, которые я еще не рассмотрел, но я думаю, что он должен быть надежным. В основном говорится: "Чтобы добавить новый коронный тип в кошелек, загляните в следующий тип монеты N, а затем добавьте количество новых монет, необходимых для создания target = N - 1". Он подсчитывает, что для этого требуется не менее ceil((target - wallet_value)/coin_value), и не проверяет, будет ли это делать каждый номер между ними. Обратите внимание, что синтаксис кодирует "от 0 до 99 центов", добавляя конечное число "100", так как это дает соответствующий окончательный target.

Причина, по которой она не проверяется, - это что-то вроде: "если это возможно, она автоматически будет". Положите более прямо, как только вы сделаете этот шаг за копейку (значение 1), алгоритм может "сломать" никель (значение 5) в любой интервал 0 - 4. Как только вы сделаете это для никеля, алгоритм теперь может "ломаться" "десять центов (значение 10). И так далее.

Конечно, для этого не требуются те или иные исходные данные; вы также можете использовать странные валюты:

>>> optimum_change(1, 4, 7, 8, 100)
[3, 1, 0, 12]

Обратите внимание, что он автоматически игнорирует 7 монет, потому что он знает, что он уже может "сломать" 8 с изменением, которое он имеет.

Ответ 17

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

Мое решение (жадный подход) в java-решении:

public class MinimumCoinDenomination {

    private static final int[] coinsDenominations = {1, 5, 10, 25, 50, 100};

    public static Map<Integer, Integer> giveCoins(int requiredCents) {
        if(requiredCents <= 0) {
            return null;
        }
        Map<Integer, Integer> denominations = new HashMap<Integer, Integer>();

        int dollar = requiredCents/100;
        if(dollar>0) {
            denominations.put(100, dollar);
        }
        requiredCents = requiredCents - (dollar * 100);

        //int sum = 0;
        while(requiredCents > 0) {
            for(int i = 1; i<coinsDenominations.length; i++) {
                if(requiredCents < coinsDenominations[i]) {
                    //sum = sum +coinsDenominations[i-1];
                    if(denominations.containsKey(coinsDenominations[i-1])) {
                        int c = denominations.get(coinsDenominations[i-1]);
                        denominations.put(coinsDenominations[i-1], c+1);
                    } else {
                        denominations.put(coinsDenominations[i-1], 1);
                    }
                    requiredCents = requiredCents - coinsDenominations[i-1];
                    break;
                }
            }
        }
        return denominations;
    }

    public static void main(String[] args) {
        System.out.println(giveCoins(199));
    }

}

Ответ 18

Прошел через это сегодня, изучая https://www.coursera.org/course/bioinformatics

DPCHANGE(money, coins)
 MinNumCoins(0) ← 0
 for m ← 1 to money
        MinNumCoins(m) ← ∞
        for i ← 1 to |coins|
            if m ≥ coini
                if MinNumCoins(m - coini) + 1 < MinNumCoins(m)
                    MinNumCoins(m) ← MinNumCoins(m - coini) + 1
    output MinNumCoins(money)

Получает разделенную запятыми строку достоинств и целевую сумму.

Реализация С#:

    public static void DPCHANGE(int val, string denoms)
    {
        int[] idenoms = Array.ConvertAll(denoms.Split(','), int.Parse);
        Array.Sort(idenoms);
        int[] minNumCoins = new int[val + 1];

        minNumCoins[0] = 0;
        for (int m = 1; m <= val; m++)
        {
            minNumCoins[m] = Int32.MaxValue - 1;
            for (int i = 1; i <= idenoms.Count() - 1; i++)
            {
                if (m >= idenoms[i])
                {
                    if (minNumCoins[m - idenoms[i]] + 1 < minNumCoins[m])
                    {
                        minNumCoins[m] = minNumCoins[m - idenoms[i]] + 1;
                    }
                }
            }
        }
    }

Ответ 19

Как я понял, если вы используете стандартные значения валютной системы, то очень легко подсчитать минимальное количество монет только одним циклом. Просто всегда используйте максимальное значение монеты, и если это невозможно, проверьте следующую опцию. Но если у вас есть такая система, как у вас есть монеты, такие как 1,2,3,4, то она не работает. Я предполагаю, что вся идея иметь монеты как 1,2,5,10,25 - сделать вычисления легкими для людей.

Ответ 20

Вот мой прием. Интересно то, что нам нужно проверить мин монеты, необходимые для формирования до coin_with_max_value (25 в нашем случае) - только 1. После этого просто вычислите сумму этих минимальных монет. С этого момента нам просто нужно добавить определенное количество coin_with_max_value, чтобы сформировать любое число до общей стоимости, в зависимости от разницы общей стоимости и найденной суммы. Что это.

Итак, для значений, которые мы принимаем, как только будут найдены монеты за 24: [1, 2, 2, 5, 10, 10]. Нам просто нужно продолжать добавлять 25 монет за каждые 25 значений, превышающих 30 (сумма мин. Монет). Итоговый ответ за 99:
[1, 2, 2, 5, 10, 10, 25, 25, 25]
9

import itertools
import math


def ByCurrentCoins(val, coins):
  for i in range(1, len(coins) + 1):
    combinations = itertools.combinations(coins, i)
    for combination in combinations:
      if sum(combination) == val:
        return True

  return False

def ExtraCoin(val, all_coins, curr_coins):
  for c in all_coins:
    if ByCurrentCoins(val, curr_coins + [c]):
      return c

def main():
  cost = 99
  coins = sorted([1, 2, 5, 10, 25], reverse=True)
  max_coin = coins[0]

  curr_coins = []
  for c in range(1, min(max_coin, cost+1)):
    if ByCurrentCoins(c, curr_coins):
      continue

    extra_coin = ExtraCoin(c, coins, curr_coins)
    if not extra_coin:
      print -1
      return

    curr_coins.append(extra_coin)

  curr_sum = sum(curr_coins)
  if cost > curr_sum:
    extra_max_coins = int(math.ceil((cost - curr_sum)/float(max_coin)))
    curr_coins.extend([max_coin for _ in range(extra_max_coins)])

  print curr_coins
  print len(curr_coins)

Ответ 21

Пример программы:

#include<stdio.h> 

    #define LEN 9 // array length
    int main(){
        int coins[LEN]={0,0,0,0,0,0,0,0,0}; // coin count
        int cointypes[LEN]={1000,500,100,50,20,10,5,2,1}; // declare your coins and note here {ASC order}   
        int sum =0; //temp variable for sum
        int inc=0; // for loop
        int amount=0; // for total amount
        printf("Enter Amount :");
        scanf("%d",&amount);
        while(sum<amount){
            if((sum+cointypes[inc])<=amount){
                   sum = sum+  cointypes[inc];
                    //printf("%d[1] - %d\n",cointypes[inc],sum);
                    //switch case to count number of notes and coin
                   switch(cointypes[inc]){
                    case 1000:
                           coins[0]++;
                           break;
                    case 500:
                           coins[1]++;
                           break;
                    case 100:
                           coins[2]++;
                           break;
                    case 50:
                           coins[3]++;
                           break;               
                    case 20:
                           coins[4]++; 
                           break;
                    case 10:
                           coins[5]++;
                           break;
                    case 5:
                           coins[6]++;
                           break;
                    case 2:
                           coins[7]++;
                           break;
                    case 1:
                           coins[8]++;
                           break;
                       }
                }else{
                   inc++;
                }
            }
        printf("note for %d in\n note 1000 * %d\n note 500 * %d\n note 100 * %d\n note 50 * %d\n note 20 * %d\n note 10 * %d\n coin 5 * %d\n coin 2 * %d\n coin 1 * %d\n",amount,coins[0],coins[1],coins[2],coins[3],coins[4],coins[5],coins[6],coins[7],coins[8]); 

    }

Ответ 22

Решение с жадным подходом в java выглядит следующим образом:

public class CoinChange {
    public static void main(String args[]) {
        int denominations[] = {1, 5, 10, 25};
        System.out.println("Total required coins are " + greeadApproach(53, denominations));
    }

    public static int greeadApproach(int amount, int denominations[]) {
        int cnt[] = new int[denominations.length];
        for (int i = denominations.length-1; amount > 0 && i >= 0; i--) {
            cnt[i] = (amount/denominations[i]);
            amount -= cnt[i] * denominations[i];            
        }
        int noOfCoins = 0;
        for (int cntVal : cnt) {
            noOfCoins+= cntVal;
        }
        return noOfCoins;
    }
}

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

Ответ 23

Здесь простое решение С# с использованием Linq.

internal class Program
{
    public static IEnumerable<Coin> Coins = new List<Coin>
    {
        new Coin {Name = "Dime", Value = 10},
        new Coin {Name = "Penny", Value = 1},
        new Coin {Name = "Nickel", Value = 5},
        new Coin {Name = "Quarter", Value = 25}
    };
    private static void Main(string[] args)
    {
        PrintChange(34);
        Console.ReadKey();
    }
    public static void PrintChange(int amount)
    {
        decimal remaining = amount;
        //Order coins by value in descending order
        var coinsDescending = Coins.OrderByDescending(v => v.Value);
        foreach (var coin in coinsDescending)
        {
            //Continue to smaller coin when current is larger than remainder
            if (remaining < coin.Value) continue;
            // Get # of coins that fit in remaining amount
            var quotient = (int)(remaining / coin.Value);

            Console.WriteLine(new string('-',28));
            Console.WriteLine("{0,10}{1,15}", coin.Name, quotient);
            //Subtract fitting coins from remaining amount
            remaining -= quotient * coin.Value;
            if (remaining <= 0) break; //Exit when no remainder left
        }
        Console.WriteLine(new string('-', 28));
    }
    public class Coin
    {
        public string Name { get; set; }
        public int Value { get; set; }
    }
}    

Ответ 24

Вдохновленный из этого https://www.youtube.com/watch?v=GafjS0FfAC0 следующий
1) оптимальная подзадача 2) Перекрывающиеся подпроцессы представленный в видеоролике

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

namespace UnitTests.moneyChange
{
    public class MoneyChangeCalc
    {
        private static int[] _coinTypes;

        private Dictionary<int, int> _solutions;

        public MoneyChangeCalc(int[] coinTypes)
        {
            _coinTypes = coinTypes;
            Reset();
        }

        public int Minimun(int amount)
        {
            for (int i = 2; i <= amount; i++)
            {
                IList<int> candidates = FulfillCandidates(i);

                try
                {
                    _solutions.Add(i, candidates.Any() ? (candidates.Min() + 1) : 0);
                }
                catch (ArgumentException)
                {
                    Console.WriteLine("key [{0}] = {1} already added", i, _solutions[i]);
                }
            }

            int minimun2;
            _solutions.TryGetValue(amount, out minimun2);

            return minimun2;
        }

        internal IList<int> FulfillCandidates(int amount)
        {
            IList<int> candidates = new List<int>(3);
            foreach (int coinType in _coinTypes)
            {
                int sub = amount - coinType;
                if (sub < 0) continue;

                int candidate;
                if (_solutions.TryGetValue(sub, out candidate))
                    candidates.Add(candidate);
            }
            return candidates;
        }

        private void Reset()
        {
            _solutions = new Dictionary<int, int>
                {
                    {0,0}, {_coinTypes[0] ,1}
                };
        }
    }
}

Тестовые случаи:

using NUnit.Framework;
using System.Collections;

namespace UnitTests.moneyChange
{
    [TestFixture]
    public class MoneyChangeTest
    {
        [TestCaseSource("TestCasesData")]
        public int Test_minimun2(int amount, int[] coinTypes)
        {
            var moneyChangeCalc = new MoneyChangeCalc(coinTypes);
            return moneyChangeCalc.Minimun(amount);
        }

        private static IEnumerable TestCasesData
        {
            get
            {
                yield return new TestCaseData(6, new[] { 1, 3, 4 }).Returns(2);
                yield return new TestCaseData(3, new[] { 2, 4, 6 }).Returns(0);
                yield return new TestCaseData(10, new[] { 1, 3, 4 }).Returns(3);
                yield return new TestCaseData(100, new[] { 1, 5, 10, 20 }).Returns(5);
            }
        }
    }
}

Ответ 25

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

public static int findMinimumNumberOfCoins(int inputCents) {

     // Error Check, If the input is 0 or lower, return 0.
     if(inputCents <= 0) return 0;

     // Create the List of Coins that We need to loop through. Start from highest to lowewst.
     // 25-10-5-1
     int[] mCoinsArray = getCoinsArray();

     // Number of Total Coins.
     int totalNumberOfCoins = 0;

     for(int i=0; i < mCoinsArray.length; i++) {

         // Get the Coin from Array.
         int coin = mCoinsArray[i];

         // If there is no inputCoin Left, simply break the for-loop
         if(inputCents == 0) break;

         // Check If we have a smaller input than our coin
         // If it's, we need to go the Next one in our Coins Array.
         // e.g, if we have 8, but the current index of array is 10, we need to go to 5.
         if(inputCents < coin) continue;

         int quotient = inputCents/coin;
         int remainder = inputCents%coin;

         // Add qutient to number of total coins.
         totalNumberOfCoins += quotient;

         // Update the input with Remainder.
         inputCents = remainder;
     }

     return totalNumberOfCoins;
 }

 // Create a Coins Array, from 25 to 1. Highest is first.
 public static int[] getCoinsArray() {

     int[] mCoinsArray = new int[4];
     mCoinsArray[0] = 25;
     mCoinsArray[1] = 10;
     mCoinsArray[2] = 5;
     mCoinsArray[3] = 1;

     return mCoinsArray;
 }

Ответ 26

Это код в С#, чтобы найти решение.

public struct CoinCount
{
    public int coinValue;
    public int noOfCoins;
}

/// <summary>
/// Find and returns the no of coins in each coins in coinSet
/// </summary>
/// <param name="coinSet">sorted coins value in assending order</param>
/// <returns></returns>
public CoinCount[] FindCoinsCountFor1to99Collection(int[] coinSet)
{
    // Add extra coin value 100 in the coin set. Since it need to find the collection upto 99.
    CoinCount[] result = new CoinCount[coinSet.Length];
    List<int> coinValues = new List<int>();
    coinValues.AddRange(coinSet);
    coinValues.Add(100);

    // Selected coin total values
    int totalCount = 0;
    for (int i = 0; i < coinValues.Count - 1; i++)
    {
        int count = 0;
        if (totalCount <= coinValues[i])
        {
            // Find the coins count
            int remainValue = coinValues[i + 1] - totalCount;
            count = (int)Math.Ceiling((remainValue * 1.0) / coinValues[i]);
        }
        else
        {
            if (totalCount <= coinValues[i + 1])
                count = 1;
            else
                count = 0;
        }
        result[i] = new CoinCount() { coinValue =  coinValues[i], noOfCoins = count };
        totalCount += coinValues[i] * count;
    }
    return result;
}

Ответ 27

import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Scanner;

public class LeastNumofCoins 
{


    public int getNumofCoins(int amount)
        {
            int denominations[]={50,25,10,5,2,1};
            int numOfCoins=0;
            int index=0;
            while(amount>0)
            {
                int coin=denominations[index];
                 if(coin==amount)
                 {
                     numOfCoins++;
                     break;
                 }
                if(coin<=amount)
                    {
                        amount=amount-coin;
                        numOfCoins++;
                    }
                    else
                    {
                        index++;
                    }

            }
            return numOfCoins;
    }
    public static void main(String[] args) throws IOException 
    {

          Scanner scanner= new Scanner(new InputStreamReader(System.in));
          System.out.println("Enter the Amount:");
          int amoount=scanner.nextInt();
          System.out.println("Number of minimum coins required to make "+ amoount +" is "+new LeastNumofCoins().getNumofCoins(amoount));
          scanner.close();
    }
}