Dynamische Programmierung Idiom für Kombinationen

Question

Betrachten Sie das Problem, in dem Sie einen Wert von N haben und Sie müssen berechnen, wie viele Möglichkeiten, wie Sie zu N Dollar summieren können [1,2,5,10,20,50,100] Dollar-Scheine mit.

Betrachten wir die klassische DP Lösung:

C = [1,2,5,10,20,50,100]

def comb(p):
    if p==0:
        return 1
    c = 0
    for x in C:
        if x <= p:
            c += comb(p-x)
    return c 

Es braucht nicht in Kraft treten, die Reihenfolge der summierten Teile. Zum Beispiel comb(4) werden 5 Ergebnisse ergeben. [1,1,1,1],[2,1,1],[1,2,1],[1,1,2],[2,2] Erwägung, dass es tatsächlich 3 ([2,1,1],[1,2,1],[1,1,2] sind alle gleich) ist

Was ist das DP-Idiom dieses Problems für die Berechnung? ( nicht-elegant Lösungen wie alle möglichen Lösungen zu erzeugen und Entfernen Duplikate sind nicht willkommen)

Answer 1

Sie sollten nicht von begining jedes Mal gehen, aber bei max aus waren, kamen Sie in jeder Tiefe. Das bedeutet, dass Sie zwei Parameter übergeben haben, beginnen und Restsumme.

C = [1,5,10,20,50,100]

def comb(p,start=0):
    if p==0:
        return 1
    c = 0
    for i,x in enumerate(C[start:]):
        if x <= p:
            c += comb(p-x,i+start)
    return c 

oder gleichwertig (es könnte besser lesbar sein)

C = [1,5,10,20,50,100]

def comb(p,start=0):
    if p==0:
        return 1
    c = 0
    for i in range(start,len(C)):
        x=C[i]
        if x <= p:
            c += comb(p-x,i)
    return c 

Answer 2

Nicht sicher über alle DP Idiome, aber man konnte mit versuchen generieren Funktionen .

Was wir finden müssen, ist der Koeffizient von x ^ N in

(1 + x + x ^ 2 + ...) (1 + x ^ 5 + x ^ 10 + ...) (1 + x ^ 10 + x ^ 20 + ...) ... ( 1 + x ^ 100 + x ^ 200 + ...)

(Anzahl der mal 1 erscheint * 1 + Anzahl der Male 5 erscheint * 5 + ...)

Welche gleich der reziproken ist von

(1-x) (1-x ^ 5) (1-x ^ 10) (1-x ^ 20) (1-x ^ 50) (1-x ^ 100).

Sie können nun jeweils in Bezug auf die Produkte der Wurzeln der Einheit, spaltete die reziproke in Bezug auf Teil Fraktionen faktorisieren (der ein ein Zeitschritt), und findet die Koeffizienten von x ^ N in jedem (das von der Form seines Polynomial / (XB)) und füge sie.

Sie könnten einige DP tun, um die Wurzeln der Einheit berechnet wird.

Answer 3

Terminologie: Was Sie suchen ist die „integer Partitionen“ in prescibed Teile (Sie sollten „Kombinationen“ im Titel ersetzen). Das Ignorieren der „dynamische Programmierung“ Teil der Frage, eine Routine für Ihr Problem ist 16 im ersten Abschnitt des Kapitels ( "Integer Partitionen", p.339ff) der fxtbook, online unter    http://www.jjj.de/fxt/#fxtbook