Динамическое программирование идиома для комбинаций - PullRequest
Новая
       20

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

3 голосов
/ 10 августа 2010

Рассмотрим проблему, в которой у вас есть значение 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 для вычисления этой проблемы?( не элегантные решения, такие как создание всех возможных решений и удаление дубликатов, не приветствуются)

Ответы [ 3 ]

7 голосов
/ 10 августа 2010

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

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

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

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

Что совпадает с обратной величиной

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

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

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

5 голосов
/ 10 августа 2010

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

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
1 голос
/ 10 августа 2010

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

...