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

Question

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

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

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

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

Answer 1

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

Answer 2

Решение с жадным подходом в 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;
    }
}

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

Answer 3

Я написал этот алгоритм для подобных проблем с 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);
    }

}

Answer 4

Вдохновленный этим 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);
            }
        }
    }
}

Answer 5

Вот мое решение, снова на 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)

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

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

Но если мы уберем одну монету, независимо от номинала, мы получим False:

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

Answer 6

Это код в c # для поиска решения.

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

Answer 7

С одной стороны, на это ответили. С другой стороны, большинство ответов требуют много строк кода. Этот ответ 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 с изменением, которое у него есть.