Dynamische Programmierung Optimaler Münzwechsel

Question

Ich habe einige dynamische Programmierprobleme überprüft, und ich hatte harte Zeit, meinen Kopf um einige Code in Bezug auf die Suche nach der kleinsten Anzahl von Münzen zu ändern.

Angenommen, wir haben Münzen im Wert von 25, 10 und 1, und wir machen eine Änderung für 30. Greedy würde 25 und 5 (1) zurückgeben, während die optimale Lösung 3 (10) zurückgeben würde. Hier ist der Code aus dem Buch zu diesem Problem:

def dpMakeChange(coinValueList,change,minCoins): 
    for cents in range(change+1): 
     coinCount = cents 
     for j in [c for c in coinValueList if c <= cents]: 
      if minCoins[cents-j] + 1 < coinCount: 
       coinCount = minCoins[cents-j]+1 
     minCoins[cents] = coinCount 
    return minCoins[change] 

Wenn mir jemand meinen Kopf wickeln um diesen Code helfen könnte (Linie 4 ist, wo ich beginnen verwirrt zu bekommen), das wäre toll. Vielen Dank!

Answer 1

Es sieht für mich so aus, als ob der Code das Problem für jeden Cent-Wert bis zum Ziel-Cent-Wert löst. In Anbetracht union(S', c), einen Zielwertes v und eine Reihe von Münzen C, wissen Sie, dass die optimale Münze Auswahl S der Form sein muss, wo c einige Münzen aus C und S' ist die optimale Lösung für v - value(c) (meine Schreibweise entschuldigen). Also das Problem hat optimal substructure. Der dynamische Programmieransatz soll alle möglichen Teilprobleme lösen. Es dauert cents * size(C) Schritte, im Gegensatz zu etwas, das viel schneller explodiert, wenn Sie nur versuchen, die direkte Lösung brutal zu erzwingen.

def dpMakeChange(coinValueList,change,minCoins): 
    # Solve the problem for each number of cents less than the target 
    for cents in range(change+1): 

     # At worst, it takes all pennies, so make that the base solution 
     coinCount = cents 

     # Try all coin values less than the current number of cents 
     for j in [c for c in coinValueList if c <= cents]: 

      # See if a solution to current number of cents minus the value 
      # of the current coin, with one more coin added is the best 
      # solution so far 
      if minCoins[cents-j] + 1 < coinCount: 
       coinCount = minCoins[cents-j]+1 

     # Memoize the solution for the current number of cents 
     minCoins[cents] = coinCount 

    # By the time we're here, we've built the solution to the overall problem, 
    # so return it 
    return minCoins[change] 

Answer 2

Ich denke, die vierte Zeile verwirrend ist, weil während Python/Filter in einer Liste Verständnis (transform(x) for x in iterable if condition(x)) auswählen kann, ist es nicht das gleiche in seinem Standard for x in iterable: Ausdruck tun.

Also eine (käsig imo) Art und Weise Menschen herumkommen, das ist die beiden zusammen zu schweißen. Sie erstellen ein Listenverständnis, das tatsächlich keine Transformation durchführt (also die c for c in coinValueList), nur damit sie die if c <= cents Klausel hinzufügen können. Und dann verwenden Sie das als iterable für einen Standard for x in iterable: Ausdruck. Ich vermute, dass da etwas von deiner Verwirrung herkommt.

Eine alternative Art und Weise, dass Zeile geschrieben zu haben gewesen sein könnte:

... 
for eachCoinValue in filter(lambda x: x <= cents, coinValueList): 
... 

Oder noch deutlicher, mit einem „Absicht enthüllt Variable“ wäre:

... 
smallEnoughCoins = filter(lambda each: each <= cents) 
for each in smallEnoughCoins: 
    ... 

Answer 3

Hier ist eine Möglichkeit, Denken Sie über das Münzwechselproblem nach, das nützlich sein könnte, wenn Sie sich mit der Graphentheorie auskennen.

Angenommen, Sie ein Diagramm in der folgenden Art und Weise definiert haben:

• Es gibt einen Knoten für jede Geldeinheit (zB ein paar Cent) von 0 bis zu dem Wert, den Sie interessiert sind (zB 39 Cent oder was auch immer.)
• Es gibt einen Bogen zwischen zwei Knoten, getrennt durch genau den Wert einer Münze, die Sie verwenden dürfen (zB ein Knoten zwischen 34 Cent und 29 Cent, wenn Sie Nickels verwenden dürfen.)

Jetzt können Sie das Münzwechselproblem als ein kürzestes p denken ath Problem von Ihrem Wert von Interesse bis auf Null, weil die Anzahl der Münzen genau die gleiche wie die Anzahl der Bögen in Ihrem Weg ist.

Der Algorithmus verwendet keine graphentheoretische Terminologie, aber er macht im Grunde dasselbe: Die äußere Schleife erstreckt sich über alle "Cents" (oder Knoten in der Graphentheorie) und die innere Schleife ist über alle Bögen (die Werte in coinValueList) vom aktuellen Bogen bis zum nächsten Bogen. Alle zusammen suchen sie den kürzesten Weg von Null bis zu Ihrem Wert von Interesse. (Wert runter auf Null, Null bis Wert, ist nicht wichtig. Traditionell suchen wir jedoch abwärts bis Null.)

Ich fing erst wirklich an, dynamische Programmierung zu verstehen, als ich erkannte, dass viele Probleme als Graphprobleme auftreten konnten. (Seien Sie vorsichtig, obwohl - nicht alle von ihnen können. Einige sind Hypergraphen, und einige sind wahrscheinlich nicht einmal das. Aber es hat mir sehr geholfen.)