webentwicklung-frage-antwort-db.com.de

Finden Sie die geringste Anzahl von Münzen, die zwischen 1 und 99 Cent geändert werden kann

Vor kurzem habe ich meinen Kollegen aufgefordert, einen Algorithmus zu schreiben, um dieses Problem zu lösen:

Finden Sie die geringste Anzahl von Münzen, die zwischen 1 und 99 Cent geändert werden kann. Die Münzen können nur Pennys (1), Nickel (5), Dime (10) und Viertel (25) sein, und Sie müssen in der Lage sein, jeden Wert von 1 bis 99 (in 1-Cent-Schritten) aus diesen Münzen zu ermitteln.

Mir wurde jedoch klar, dass ich nicht weiß, wie ich das selbst machen kann, ohne jede mögliche Kombination von Münzen zu untersuchen. Es muss einen besseren Weg geben, um dieses Problem zu lösen, aber ich weiß nicht, wie der generische Name für diese Art von Algorithmus heißen würde, und ich kann keinen Weg finden, ihn zu vereinfachen, abgesehen von jeder Lösung.

Ich habe mich gefragt, ob mich jemand in die richtige Richtung weisen oder einen Algorithmus anbieten könnte, der effizienter ist.

60
Daniel T.

Was Sie suchen, ist Dynamische Programmierung .

Sie müssen nicht alle möglichen Kombinationen für alle möglichen Werte auflisten, da Sie sie auf den vorherigen Antworten aufbauen können.

Ihr Algorithmus muss 2 Parameter annehmen:

  • Die Liste der möglichen Münzwerte, hier [1, 5, 10, 25]
  • Der abzudeckende Bereich, hier [1, 99]

Ziel ist es, die für diesen Bereich erforderliche Mindestmenge an Münzen zu berechnen.

Der einfachste Weg ist, von unten nach oben vorzugehen:

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

Es ist einigermaßen einfach, bei jedem Schritt können wir höchstens eine Münze hinzufügen, wir müssen nur wissen, wo. Dies läuft darauf hinaus, dass der Bereich [x,y] in [x,y+1] enthalten ist. Daher sollte der minimale Satz für [x,y+1] den minimalen Satz für [x,y] enthalten.

Wie Sie vielleicht schon bemerkt haben, gibt es manchmal Unentschiedenheiten, dh mehrere Sätze haben die gleiche Anzahl von Münzen. In diesem Fall kann erst später entschieden werden, welche davon verworfen werden soll.

Es sollte möglich sein, die Laufzeit zu verbessern, wenn man feststellt, dass man durch das Hinzufügen einer Münze in der Regel einen weit größeren Bereich abdecken kann als der, für den man sie hinzugefügt hat, denke ich.

Beachten Sie zum Beispiel Folgendes:

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

wir fügen ein Nickel hinzu, um [1,5] abzudecken, aber das gibt uns kostenlos [1,9]!

Beim Umgang mit unerhörten Eingabesätzen [2,3,5,10,25] zur Abdeckung von [2,99] bin ich mir jedoch nicht sicher, wie der von dem neuen Satz abgedeckte Bereich schnell überprüft werden kann, oder er wäre tatsächlich effizienter.

23
Matthieu M.

Sie können sehr schnell eine obere Grenze finden.

Sagen Sie, Sie nehmen drei Viertel. Dann müssten Sie nur die "Lücken" 1-24, 26-49, 51-74, 76-99 mit anderen Münzen füllen.

Trivial würde das mit 2 Dimes, 1 Nickel und 4 Pennys funktionieren.

Daher sollte 3 + 4 + 2 + 1 eine Obergrenze für die Anzahl der Münzen sein. Wenn Ihr Algorithmus für Brute-Force-Werte den Wert übersteigt, können Sie sofort mit der Suche aufhören.

Der Rest der Suche sollte für alle Zwecke mit dynamischer Programmierung schnell genug sein.

(edit: feste Antwort nach Gabes Beobachtung)

9
Thomas

Ich habe über dynamische Programmierung heute gelernt und hier ist das Ergebnis:

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]

Dynamische Programmierung ist wirklich magisch.

7
sumzup

Sie benötigen mindestens 4 Pennys, da Sie 4 als Änderung erhalten möchten, und Sie können dies nur mit Pennys tun.

Es ist nicht optimal, mehr als vier Cent zu haben. Anstelle von 4 + x Pfennigen können Sie 4 Pfennige und x Nickel haben - sie umfassen mindestens den gleichen Bereich.

Sie haben also genau 4 Pfennige.

Sie benötigen mindestens 1 Nickel, da Sie als Änderung 5 erhalten möchten.

Es ist nicht optimal, mehr als 1 Nickel zu haben. Anstelle von 1 + x Nickel können Sie 1 Nickel und X-Dimen haben - sie erstrecken sich mindestens über den gleichen Bereich.

Sie haben also genau 1 Nickel.

Du brauchst mindestens 2 Dimes, da du 20 bekommen willst.

Das bedeutet, dass Sie 4 Pennys, 1 Nickel und mindestens 2 Dimen haben.

Wenn Sie weniger als 10 Münzen hätten, hätten Sie weniger als 3 Viertel. Aber die maximal mögliche Änderung, die Sie mit allen Münzen erhalten könnten, ist 4 + 5 + 20 + 50 = 79, nicht genug.

Das heißt, Sie haben mindestens 10 Münzen. Thomas Antwort zeigt, dass in der Tat alles gut ist, wenn Sie 4 Pfennige, 1 Nickel, 2 Dimes und 3 Viertel haben.

7
sdcvvc

Gute Frage. Dies ist die Logik, die ich mir ausgedacht habe. Getestet mit wenigen Szenarien, darunter 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);
    }
}

Einige Ergebnisse: Wenn maxCurrencyLevelForTest = 25

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

Wenn maxCurrencyLevelForTest = 99 ist

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

Ich denke, der Code kann weiter überarbeitet werden.

4
SKG

Edit: Wie die Kommentatoren festgestellt haben, habe ich die Frage falsch interpretiert. (Die Frage ist sehr ähnlich zu einem grundlegenden CS-Problem, das ich an Studenten am College zu lösen sehe ...) waves hand Dies ist nicht die Antwort, die Sie suchen. Das heißt, obwohl die ursprüngliche Antwort falsch ist, können wir sie als Sprungbrett für eine O (n) -Lösung verwenden.

Nehmen Sie also unten die falsche Antwort, die nur einen einzelnen Wert (dh die für 68 Cent erforderliche Mindestprägung) löst, und führen Sie sie einfach für jeden Wert aus.

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)]

Nun, dies wird Ihnen sicherlich eine gültige Antwort geben, aber ist es eine minimale Antwort? (Dies ist der schwierigere Teil. Zur Zeit sagt mein Bauch ja, aber ich denke immer noch darüber nach ...)


( Die falsche Antwort )

Beeindruckend. Schleifen Dynamische Programmierung? Wirklich Leute?

In Python:

amount = ( your_amount_in_cents )

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

Wahrscheinlich können einige dieser Modulo-Operationen vereinfacht werden ...

Das ist nicht schwer, Sie müssen nur darüber nachdenken, wie Sie im wirklichen Leben Veränderungen vornehmen. Sie geben Quartale aus, bis Sie durch Hinzufügen eines weiteren Viertels die gewünschte Menge übersteigen, und Sie geben Dimen aus, bis Sie durch das Hinzufügen eines weiteren Dime die gewünschte Menge erreichen. Dann konvertieren Sie in mathematische Operationen: Modulo und Division. Die gleiche Lösung gilt für Dollar, die Sekunden werden in HH: MM: SS usw. umgewandelt.

3
Thanatos

Angenommen, Sie sprechen von US-Währung, möchten Sie einen gierigen Algorithmus: http://en.wikipedia.org/wiki/Greedy_algorithm

Im Wesentlichen probieren Sie alle Werte von der höchsten zur niedrigsten aus und nehmen so viele Münzen wie möglich von jedem Wert, bis Sie nichts mehr übrig haben.

Für den allgemeinen Fall siehe http://en.wikipedia.org/wiki/Change-making_problem , weil Sie dynamische Programmierung oder lineare Programmierung verwenden möchten, um die Antwort für beliebige Bezeichnungen zu finden, bei denen ein gieriger Algorithmus nicht wäre Arbeit.

2
Gabe

Nachdem ich keine gute Lösung für diese Art von Problemen in PHP gefunden hatte, entwickelte ich diese Funktion. 

Es kostet einen beliebigen Geldbetrag (bis zu 999,99 US-Dollar) und gibt ein Array der Mindestanzahl jeder Banknote/Münze zurück, die erforderlich ist, um diesen Wert zu erhalten.

Der Wert wird zuerst in ein Penny in ein int konvertiert (aus irgendeinem Grund würde ich am Ende bei der Verwendung von Standard-Float-Werten zu Fehlern kommen). 

Die zurückgegebenen Nennwerte sind ebenfalls in Pennys (dh: 5000 = $ 50, 100 = $ 1 usw.).

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
2
user3537590

Die Aufgabe

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

unterscheidet sich von der Aufgabe

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

denn die Lösung könnte ein völlig anderes Multiset von Münzen sein.

Angenommen, Sie haben keine (1), (5), (10) und (25) Cent-Münzen, sondern (1), (3), (5) und (17) Cent-Münzen: Um die Änderung vorzunehmen für 5 brauchen Sie nur eine (5) Münze; aber für alle Änderungen von 1 bis 5 benötigen Sie zwei (1) Münzen und eine (3) Münze, keine (5) Münze.

Der gierige Algorithmus wird vom kleinsten zum größten Wert in Bezug auf die Änderungswerte und Münzwerte iteriert:

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...

Das ist in 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]

Und in 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;
}
1
comonad

Dieses könnte eine generische Lösung in C # sein.

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

Ich habe es nicht ganz durchdacht ... es ist zu spät in der Nacht. Ich dachte, die Antwort sollte in diesem Fall 9 sein, aber Gabe sagte, es sollte 10 sein ... was genau das ergibt. Ich denke, es hängt davon ab, wie Sie die Frage interpretieren ... suchen wir nach der kleinsten Anzahl von Münzen, die einen Wert <= X erzeugen kann, oder nach der geringsten Anzahl von Münzen, die einen Wert <= X mit der geringsten Anzahl von Münzen erzeugen kann ? Zum Beispiel ... Ich bin mir ziemlich sicher, dass wir mit nur 9 Münzen einen Wert erzielen können, ohne Nickel, aber dann um 9 zu produzieren ... Sie brauchen ... oh ... ich verstehe. Sie würden 9 Pfennige brauchen, die Sie nicht haben, weil wir das nicht gewählt haben ... in diesem Fall, ich denke diese Antwort ist richtig. Nur eine rekursive Umsetzung von Thomas 'Idee, aber ich weiß nicht, warum er dort aufgehört hat ... Sie müssen nichts brutal erzwingen.

Edit: Das sei falsch.

1
mpen

Eine Vb-Version

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
0
dbasnett

Es gibt ein paar ähnliche Antworten, aber meine Lösung mit Java scheint etwas einfacher zu verstehen. Schau dir das an.

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

Kamen heute durch dieses Thema und studierten 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)

Übernimmt eine durch Kommas getrennte Folge von Bezeichnungen und die Zielmenge.

C # -Implementierung:

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

Wie ich verstanden habe, wenn Sie Standardwerte für das Währungssystem verwenden, ist es sehr einfach, die minimale Anzahl von Münzen durch eine einzige Schleife zu zählen. Verbrauchen Sie immer den maximalen Münzenwert und prüfen Sie, ob die nächste Option verfügbar ist. Aber wenn Sie ein System wie Sie haben, wie 1,2,3,4, dann funktioniert es nicht. Ich denke, die Idee von Münzen als 1,2,5,10,25 besteht darin, den Menschen die Berechnung zu erleichtern.

0
dinesh707

Für dieses Problem bietet Greedy eine bessere Lösung als DP oder andere. Gieriger Ansatz: Ermitteln Sie die größte Stückelung, die unter dem erforderlichen Wert liegt, und addieren Sie diese zu den zu liefernden Münzen. Senken Sie die erforderlichen Cents um den gerade hinzugefügten Nennwert und wiederholen Sie den Vorgang, bis die erforderlichen Cents Null werden.

Meine Lösung (gieriger Ansatz) in Java-Lösung:

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

}
0
Jeya

Wenn Sie Ihre Münzen COIN [] und Ihren "Wechselbereich" 1..MAX haben, sollte im Allgemeinen die maximale Anzahl von Münzen ermittelt werden.

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

Ich weiß nicht, ob die Überprüfung auf Münzminimalität in den inneren Bedingungen streng genommen notwendig ist. Ich würde denken, dass die minimale Kette von Münzergänzungen richtig wäre, aber sicherer als leid.

0
Vatine

Hier ist eine einfache c # -Lösung mit 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; }
    }
}    
0
Vlad

Hier ist mein Take . Eine interessante Sache ist, dass wir die Mindestmünzen überprüfen müssen, die erforderlich sind, um den Wert von coin_with_max_value (25 in unserem Fall) zu bilden. Von diesem Punkt müssen wir nur eine bestimmte Anzahl von coin_with_max_value hinzufügen, um eine beliebige Zahl bis zu den Gesamtkosten zu bilden, abhängig von der Differenz der Gesamtkosten und der ermittelten Summe. Das ist es.

Für Werte, die wir genommen haben, gilt: Sobald min für 24 Münzen gefunden wurde, werden folgende Werte ermittelt: [1, 2, 2, 5, 10, 10] . Wir müssen nur noch 25 Münzen für alle 25 Werte hinzufügen, die 30 übersteigen (Summe von min münzen) . Die endgültige Antwort für 99 lautet:
[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)
0
i_am_saurabh

Hier ist eine einfache Version in 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

Wenn es ausgeführt wird, wird Folgendes in stdout gedruckt.

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

Der Code ist ziemlich selbsterklärend (danke Python!), Aber im Grunde ist es der Algorithmus, die größte verfügbare Münze hinzuzufügen, die Sie nicht über den aktuellen Gesamtbetrag, für den Sie suchen, in Ihre temporäre Liste von Münzen einfügt (in diesem Fall t) ). Wenn Sie die effizienteste Münzgruppe für eine bestimmte Summe gefunden haben, stellen Sie sicher, dass mindestens jede Münze in der erforderlichen Liste enthalten ist. Tun Sie das für jede Summe von 1 bis 99 Cent, und Sie sind fertig.

0
Zeke

Ich habe diesen Algorithmus für ähnliche Probleme mit DP geschrieben

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

}
0

Lösung mit Greedy-Ansatz in Java ist wie folgt: 

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

Dies funktioniert jedoch für eine einzelne Menge. Wenn Sie es für den Bereich ausführen möchten, müssen wir es für jeden Bereich angeben.

0
Ashok

Hier geht meine Lösung, wieder in Python und mittels dynamischer Programmierung. Als Erstes erzeuge ich die Mindestfolge von Münzen, die für die Änderung eines Betrags im Bereich von 1,99 erforderlich sind, und ermittle aus diesem Ergebnis die maximale Anzahl von Münzen, die für jeden Nennwert erforderlich sind:

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

Die Ausführung von min_any_change() liefert die Antwort, nach der wir gesucht haben: {'pennies': 4, 'nickels': 1, 'dimes': 2, 'quarters': 3}. Als Test können wir versuchen, eine Münze mit einem Nennwert zu entfernen und zu prüfen, ob es noch möglich ist, für jeden Betrag im Bereich 1..99 eine Änderung vorzunehmen:

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)

Wenn wir das oben erhaltene Ergebnis testen, erhalten wir eine True:

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

Wenn wir jedoch eine einzelne Münze entnehmen, wird unabhängig von der Stückelung eine False angezeigt:

test([1, 1, 1, 5, 10, 10, 25, 25, 25])
0
Óscar López

Inspiriert von diesem https://www.youtube.com/watch?v=GafjS0FfAC0 Folgt
1) Optimales Subproblem 2) Überlappende Subproblemprinzipien Einführung in das Video

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

Testfälle:

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);
            }
        }
    }
}
0
yi.han

Zum einen wurde dies beantwortet. Andererseits erfordern die meisten Antworten viele Codezeilen. Diese Python-Antwort erfordert nicht viele Codezeilen, nur viele Gedankenzeilen ^ _ ^:

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]

Dies ist ein sehr einfacher Algorithmus für die Neuskalierung, der möglicherweise für Eingaben bricht, die ich noch nicht berücksichtigt habe, aber ich denke, er sollte robust sein. Im Wesentlichen heißt es, "einen neuen Münzentyp zur Brieftasche hinzuzufügen, auf den nächsten Münztyp N zu schauen und dann die Menge an neuen Münzen hinzuzufügen, die erforderlich ist, um target = N - 1 zu machen." Es berechnet, dass Sie mindestens ceil((target - wallet_value)/coin_value) dafür benötigen, und prüft nicht, ob dies auch jede Zahl dazwischen macht. Beachten Sie, dass die Syntax die "von 0 bis 99 Cent" codiert, indem Sie die letzte Zahl "100" anhängen, da dies die entsprechende letzte Variable target ergibt. 

Der Grund, warum es nicht prüft, ist so etwas wie "wenn es möglich ist, wird es automatisch". Direkter ausgedrückt: Wenn Sie diesen Schritt für einen Cent (Wert 1) ausführen, kann der Algorithmus ein Nickel (Wert 5) in ein beliebiges Subintervall 0 - 4 "brechen". Wenn Sie es für einen Nickel tun, kann der Algorithmus jetzt "brechen" "einen Cent (Wert 10). Und so weiter.

Natürlich sind diese besonderen Eingaben nicht erforderlich. Sie können auch fremde Währungen verwenden:

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

Beachten Sie, dass die 7-Münze automatisch ignoriert wird, da sie weiß, dass sie bereits 8 mit der Änderung "zerbrechen" kann.

0
CR Drost

Dies ist der Code in c #, um die Lösung zu finden.

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

Beispielprogramm:

#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]); 

    }
0
Elshan