Dynamische Programmierung - Münze Änderung Entscheidung

Question

Ich bin die Überprüfung einiger alte Notizen von meinem Algorithmen Kurs und die dynamischen Probleme der Programmierung sind scheinbar ein bisschen schwierig für mich. Ich habe ein Problem, wo wir einen unbegrenzten Vorrat an Münzen haben, mit einigen Konfessionen x1, x2, ... xn und wir wollen Veränderung für einen Wert X machen Wir versuchen, ein dynamisches Programm zu entwerfen, ob für X Änderung entscheiden kann gemacht wird oder nicht (nicht die Anzahl der Münzen zu minimieren, oder Rückkehr, welche Münzen, nur wahr oder falsch).

Ich habe einige Gedanken über dieses Problem gemacht, und ich kann eine rekursive Methode, dies zu tun, wo es so etwas wie ...

siehe

MakeChange(X, x[1..n this is the coins])
    for (int i = 1; i < n; i++)
    {
        if ( (X - x[i] ==0) || MakeChange(X - x[i]) )
            return true;
    }
    return false;

Converting dies ein dynamisches Programm kommt nicht so leicht für mich. Wie könnte ich diesen Ansatz?

Answer 1

Der Code ist ein guter Anfang. Der üblicher Weg, eine rekursive Lösung zu einem dynamischen Programmierung umzuwandeln ist, es zu tun „bottom-up“ statt „top-down“. Das heißt, wenn Sie Ihre rekursive Lösung berechnet etwas für eine bestimmte X-Werte für kleinere x verwenden, dann stattdessen die gleiche Sache berechnen Start in kleineren x, und es in einer Tabelle setzen.

In Ihrem Fall, ändern Sie Ihre MakeChange rekursive Funktion in eine canMakeChange Tabelle.

canMakeChange[0] = True
for X = 1 to (your max value):
   canMakeChange[X] = False
   for i=1 to n:
     if X>=x[i] and canMakeChange[X-x[i]]==True: 
       canMakeChange[X]=True

Answer 2

Meine Lösung ist ein gieriger Ansatz alle Lösungen und Cachen der neueste optimale einer Berechnung. Wenn die aktuelle Ausführung Lösung ist bereits größer als gespeicherte Lösung Abbruch des Pfades. Beachten Sie, für die beste Leistung Stückelung in absteigender Reihenfolge sein sollte.

import java.util.ArrayList;
import java.util.List;

public class CoinDenomination {

    int denomination[] = new int[]{50,33,21,2,1};
    int minCoins=Integer.MAX_VALUE;
    String path;

    class Node{
        public int coinValue;
        public int amtRemaining;
        public int solutionLength;
        public String path="";
        public List<Node> next;

        public String toString() { return "C: "+coinValue+" A: "+amtRemaining+" S:"+solutionLength;}
    }

    public List<Node> build(Node node)
    {
        if(node.amtRemaining==0)
        {
            if (minCoins>node.solutionLength) {
                minCoins=node.solutionLength;
                path=node.path;
            }
            return null;
        }

        if (node.solutionLength==minCoins) return null;
        List<Node> nodes = new ArrayList<Node>();
        for(int deno:denomination)
        {
           if(node.amtRemaining>=deno)
           {
               Node nextNode = new Node();
               nextNode.amtRemaining=node.amtRemaining-deno;
               nextNode.coinValue=deno;
               nextNode.solutionLength=node.solutionLength+1;
               nextNode.path=node.path+"->"+deno;
               System.out.println(node);
               nextNode.next = build(nextNode);
               nodes.add(node);

           }
        }

        return nodes;
    }

    public void start(int value)
    {
        Node root = new Node();
        root.amtRemaining=value;
        root.solutionLength=0;
        root.path="start";
        root.next=build(root);
        System.out.println("Smallest solution of coins count: "+minCoins+" \nCoins: "+path);
    }

    public static void main(String args[])
    {
        CoinDenomination coin = new CoinDenomination();
        coin.start(35);
    }
}

Answer 3

Fügen Sie einfach einen memoization Schritt auf die rekursive Lösung, und der dynamische Algorithmus fällt direkt aus ihm heraus. Das folgende Beispiel ist in Python:

cache = {}
def makeChange(amount, coins):
    if (amount,coins) in cache:
        return cache[amount, coins]
    if amount == 0:
        ret = True
    elif not coins:
        ret = False
    elif amount < 0:
        ret = False 
    else:
        ret = makeChange(amount-coins[0], coins) or makeChange(amount, coins[1:])
    cache[amount, coins] = ret
    return ret

Natürlich können Sie ein Dekorateur Auto-memoize verwenden könnten, um mehr natürlichen Code führen:

def memoize(f):
    cache = {}
    def ret(*args):
        if args not in cache:
            cache[args] = f(*args)
        return cache[args]
    return ret
@memoize
def makeChange(amount, coins):
    if amount == 0:
        return True
    elif not coins:
        return False
    elif amount < 0:
        return False
    return makeChange(amount-coins[0], coins) or makeChange(amount, coins[1:])

. Hinweis: auch die nicht-dynamisch-Programmierung Version zurückgeschrieben Sie alle Arten von Grenzfällen Bugs haben, weshalb die makeChange oben sind etwas länger als deine

Answer 4

Dieses Papier ist sehr relevant: http://ecommons.library.cornell.edu / Griff / 1813/6219

Im Grunde genommen wie andere gesagt haben, optimal den Wandel eines beliebigen X mit beliebigen Stückelung Sätzen in Höhe von NP-Hard, dynamische Programmierung bedeutet nicht rechtzeitig Algorithmus ergeben. Dieses Papier schlägt eine Polynom-Zeit (das heißt, Polynom in der Größe des Eingangs, was eine Verbesserung gegenüber früheren Algorithmen) zur Bestimmung Algorithmus, wenn der Greedy-Algorithmus erzeugt immer optimale Ergebnisse für einen bestimmten Satz von Konfessionen.

Answer 5

Hier ist c # -Version nur als Referenz, die minimale Anzahl von Münzen für bestimmte Summe erforderlich zu finden:

(kann man in meinem Blog verweisen @ http://codingworkout.blogspot.com/2014/08/coin-change-subset-sum-problem-with.html für weitere Details)

public int DP_CoinChange_GetMinimalDemoninations(int[] coins, int sum)
        {
            coins.ThrowIfNull("coins");
            coins.Throw("coins", c => c.Length == 0 || c.Any(ci => ci <= 0));
            sum.Throw("sum", s => s <= 0);
            int[][] DP_Cache = new int[coins.Length + 1][];
            for (int i = 0; i <= coins.Length; i++)
            {
                DP_Cache[i] = new int[sum + 1];
            }
            for(int i = 1;i<=coins.Length;i++)
            {
                for(int s=0;s<=sum;s++)
                {
                    if (coins[i - 1] == s)
                    {
                        //k, we can get to sum using just the current coin
                        //so, assign to 1, no need to process further
                        DP_Cache[i][s] = 1;
                    }
                    else 
                    {
                        //initialize the value withouth the current value
                        int minNoOfCounsWithoutUsingCurrentCoin_I = DP_Cache[i - 1][s];
                        DP_Cache[i][s] = minNoOfCounsWithoutUsingCurrentCoin_I;
                        if ((s > coins[i - 1]) //current coin can particiapte
                            && (DP_Cache[i][s - coins[i - 1]] != 0))
                        {
                            int noOfCoinsUsedIncludingCurrentCoin_I = 
                                DP_Cache[i][s - coins[i - 1]] + 1;
                            if (minNoOfCounsWithoutUsingCurrentCoin_I == 0)
                            {
                                //so far we couldnt identify coins that sums to 's'
                                DP_Cache[i][s] = noOfCoinsUsedIncludingCurrentCoin_I;
                            }
                            else
                            {   
                                int min = this.Min(noOfCoinsUsedIncludingCurrentCoin_I, 
                                    minNoOfCounsWithoutUsingCurrentCoin_I);
                                DP_Cache[i][s] = min;
                            }
                        }
                    }
                }
            }
            return DP_Cache[coins.Length][sum];
        }

Answer 6

Im allgemeinen Fall, wo Münzwerte beliebig sein kann, das Problem, das Sie präsentieren genannt wird der Knapsack Problem und ist dafür bekannt, NP-vollständig ( Pearson, D. 2004 ), so ist daher nicht auflösbar in Polynomzeit wie dynamische Programmierung.

Nehmen Sie das pathologische Beispiel von x [2] = 51, x [1] = 50, x [0] = 1, X = 100. Dann ist es erforderlich, dass der Algorithmus 'prüfen', um die Möglichkeiten des mit Münzwechsel machen x [2], alternativ der Wandel Anfang mit x [1]. Der erste Schritt mit nationaler Prägung verwendet, auch bekannt als die Greedy-Algorithmus - nicht Arbeit mit pathologischen Prägungen nämlich , „weniger die größte Münze verwenden als die Arbeits insgesamt,“ werden. Stattdessen erleben solche Algorithmen, um eine kombinatorische Explosion, dass qualifiziert sie in NP-vollständig.

Für bestimmte Sonder Münzwert Anordnungen, wie praktisch alle, die in der tatsächlichen Verwendung, einschließlich der fiktiven Sytem X [i + 1] == 2 * X [i], gibt es sehr schnelle Algorithmen, auch O (1) in dem fiktiven Fall gegeben, die beste Leistung zu bestimmen. Diese Algorithmen ausnutzen Eigenschaften der Münzwerte.

Ich bin mir nicht bewusst eine dynamische Programmierlösung: ein, die den Vorteil der optimalen Unter Lösungen nimmt entsprechend der Programmierung Motiv erforderlich. Im Allgemeinen ein Problem kann nur durch die dynamische Programmierung gelöst werden, wenn es in Teilprobleme zerlegt werden kann, die, wenn sie optimal gelöst, kann wieder zusammengesetzt in eine Lösung sein, die beweisbar optimal ist. Das heißt, wenn der Programmierer nicht mathematisch nachweisen kann ( „beweisen“), dass das Wiederzusammensetzen optimale Unter Lösungen des Problems führt zu einer optimalen Lösung, dann dynamische Programmierung nicht angewendet werden kann.

Ein Beispiel häufig der dynamischen Programmierung gegeben ist eine Anwendung mehr Matrizen zu multiplizieren. Je nach Größe der Matrizen, um die Wahl zu bewerten A · B · C als eine der beiden äquivalenten Formen: (( A · B ) · C ) oder ( A · ( B · C )) führt zu den Berechnungen von verschiedenen Mengen von Multiplikationen und Additionen. Das heißt, ein Verfahren optimalere (schneller) als die andere Methode. Dynamische Programmierung ist ein Motiv, das tabellarisch die Berechnungskosten der verschiedenen Methoden, und führt die tatsächlichen Berechnungen nach einem Zeitplan (oder Programm ) berechnet dynamisch zur Laufzeit.

Ein wesentliches Merkmal ist, dass Berechnungen nach dem berechneten Zeitplan durchgeführt werden und nicht durch eine Aufzählung aller möglichen Kombinationen - ob die Aufzählung rekursiv durchgeführt wird oder iterativ. Im Beispiel von Matrizes Multiplikation, bei jedem Schritt nur die Least-Cost-Multiplikation gewählt wird. Als Folge werden die möglichen Kosten für die Zwischen Kosten suboptimalen Zeitpläne nie berechnet. Mit anderen Worten, ist der Zeitplan nicht durch die Suche alle möglichen Zeitpläne für die optimale berechnet, sondern durch einen optimalen Zeitplan aus dem Nichts schrittweise aufzubauen.

Die Nomenklatur ‚dynamische Programmierung‘ verglichen werden kann mit ‚linearer Programmierung‘, in der ‚Programm‘ auch im Sinne Bedeutung verwendet ‚Plan.‘

Weitere Informationen über die dynamische Programmierung Um zu erfahren, besuchen Sie das größte Buch über Algorithmen noch zu mir bekannt, "Introduction to Algorithms" von Cormen, Leiserson, Rivest und Stein. "Rivest" ist die 'R' von "RSA" und den dynamischen Programmierungist aber ein Kapitel von Partituren.

Answer 7

Wenn Sie in einer rekursiven Weise schreiben, es ist in Ordnung, nur die Verwendung speicherbasierte Suche. Sie haben zu speichern, was Sie berechnet haben, die nicht erneut berechnet werden

int memory[#(coins)]; //initialize it to be -1, which means hasn't been calculated
MakeChange(X, x[1..n this is the coins], i){
    if(memory[i]!=-1) return memory[i];
    for (int i = 1; i < n; i++)
    {
        if ( (X - x[i] ==0) || MakeChange(X - x[i], i) ){
            memory[i]=true;
            return true;
        }
    }
    return false;
}