Idiome de programmation dynamique pour les combinaisons

Question

Considérez le problème dans lequel vous avez une valeur de N et vous devez calculer combien de façons vous pouvez résumer à N dollars en utilisant [1,2,5,10,20,50,100] Dollars.

la solution DP Tenir compte classique:

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 

Il ne prend pas en effet l'ordre des parties totalisées. Par exemple, comb(4) donnera 5 résultats: [1,1,1,1],[2,1,1],[1,2,1],[1,1,2],[2,2] alors qu'il y a actuellement 3 résultats ([2,1,1],[1,2,1],[1,1,2] sont tous les mêmes).

Quelle est l'idiome DP pour calculer ce problème? ( non élégantes solutions telles que la génération de toutes les solutions possibles et la suppression des doublons ne sont pas les bienvenus)

Answer 1

Vous ne devriez pas aller du début à chaque fois, mais à partir de laquelle vous veniez à chaque profondeur. Cela signifie que vous devez passer deux paramètres, commencer et reste total.

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 

ou équivalent (il pourrait être plus facile à lire)

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

ne suis pas sûr des idiomes DP, mais vous pouvez essayer d'utiliser Generating Functions.

Ce que nous devons trouver est le coefficient de x^N dans

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

(nombre de fois 1 apparaît * 1 + nombre de fois 5 apparaît * 5 + ...)

qui est identique à l'inverse de

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

Vous pouvez maintenant factoriser chacun en termes de produits de racines d'unité, diviser l'inverse en termes de Partial Fractions (qui est un pas de temps) et trouver le coefficient de x^N dans chacun (qui sera de la forme Polynomial/(xw)) et additionnez-les.

Vous pourriez faire un peu de DP dans le calcul des racines de l'unité.

Answer 3

Terminologie: Ce que vous recherchez est les « partitions entières » en parties prescibed (vous devez remplacer « combinaisons » dans le titre). Ignorant la partie de la question « programmation dynamique », une routine pour votre problème est donnée dans la première section du chapitre 16 (« partitions entières », p.339ff) du fxtbook, en ligne à http://www.jjj.de/fxt/#fxtbook