linguaggio di programmazione dinamica per combinazioni

Question

Si consideri il problema in cui si dispone di un valore di N ed è necessario calcolare quanti modi si può riassumere a dollari N usando bollette [1,2,5,10,20,50,100] dollaro.

Si consideri la soluzione classica DP:

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 

Non ci vuole in vigore l'ordine delle parti sommati. Ad esempio, sarà resa comb(4) 5 risultati:. [1,1,1,1],[2,1,1],[1,2,1],[1,1,2],[2,2] considerando che sono in realtà 3 Risultati ([2,1,1],[1,2,1],[1,1,2] sono tutti uguali)

Qual è il linguaggio DP per il calcolo di questo problema? ( non elegante soluzioni quali la generazione di tutte le possibili soluzioni e la rimozione dei duplicati non sono i benvenuti)

Answer 1

Non si dovrebbe andare dal begining di volta in volta, ma al massimo da eri venuto da a ciascuna profondità. Questo significa che si deve passare due parametri, avviare e totale rimanente.

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 

o equivalente (potrebbe essere più leggibile)

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

Non è sicuro su eventuali idiomi DP, ma si potrebbe provare a utilizzare funzioni generatrici .

Quello che dobbiamo trovare è il coefficiente di x ^ N in

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

(numero di volte 1 appare * 1 + numero di volte in 5 appare * 5 + ...)

che è lo stesso come il reciproco della

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

È ora possibile fattorizzare ciascuno in termini di prodotti di radici dell'unità, dividere il reciproco in termini di frazioni parziali (che è un unico passaggio) e trovare il coefficiente di x ^ N in ciascuna (che sarà di forma polinomiale / (xw)) e sommare.

Si potrebbe fare un po 'DP nel calcolo delle radici di unità.

Answer 3

Terminologia: Quello che state cercando è il "partizioni interi" in parti prescibed (è necessario sostituire "combinazioni" nel titolo). Ignorando la parte "programmazione dinamica" della questione, una routine per il vostro problema è dato nella prima sezione del capitolo 16 ( "partizioni integer", p.339ff) del fxtbook, online su    http://www.jjj.de/fxt/#fxtbook