Идиома динамического программирования для комбинаций

Question

Рассмотрите проблему, в которой у вас есть значение N, и вам нужно рассчитать, сколько способов вы можете суммировать до N долларов, используя [1,2,5,10,20,50,100] Долларовые счета.

Рассмотрим классическое решение 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 

Он не принимает в силу порядок суммированных частей. Например, comb(4) даст 5 результатов: [1,1,1,1],[2,1,1],[1,2,1],[1,1,2],[2,2], тогда как на самом деле есть 3 результата ([2,1,1],[1,2,1],[1,1,2] - все одинаковые).

Что такое DP idiom для расчета этой проблемы? (неэлементные решения, такие как создание всех возможных решений и удаление дубликатов, не приветствуются)

Answer 1

Вы не должны уходить от начала каждый раз, но при макс. От того, что вы пришли с каждой глубины. Это означает, что вам нужно передать два параметра, начать и оставшуюся сумму.

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 

или эквивалент (это может быть более удобным для чтения)

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

Не уверен ни о каких DP-идиомах, но вы можете попробовать использовать Generating Functions.

Что нам нужно найти это коэффициент х^N в

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

(количество раз 1 появляется * 1 + количество раз 5 появляется * 5 + ...)

Что же, как величина, обратная

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

Теперь вы можете разложить каждый по продуктам корней единства, разделить взаимные в терминах Partial Fractions (что является одноразовым шагом) и найти коэффициент при x^N в каждом (который будет иметь вид Полином/(xw)) и добавьте их.

Вы можете сделать некоторый DP при расчете корней единства.

Answer 3

Терминология: Что вы ищете в «целые разделы» в prescibed части (Вы должны заменить «комбинации» в названии). Игнорирование «динамическое программирование» часть вопроса, рутинной вашей проблемы дается в первой части главы 16 («разбиений», p.339ff) из fxtbook, на сайте http://www.jjj.de/fxt/#fxtbook