Dynamic programming idiom for combinations

Question

Consider the problem in which you have a value of N and you need to calculate how many ways you can sum up to N dollars using [1,2,5,10,20,50,100] Dollar bills.

Consider the classic DP solution:

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 

It does not take into effect the order of the summed parts. For example, comb(4) will yield 5 results: [1,1,1,1],[2,1,1],[1,2,1],[1,1,2],[2,2] whereas there are actually 3 results ([2,1,1],[1,2,1],[1,1,2] are all the same).

What is the DP idiom for calculating this problem? (non-elegant solutions such as generating all possible solutions and removing duplicates are not welcome)

Answer 1

Not sure about any DP idioms, but you could try using Generating Functions.

What we need to find is the coefficient of x^N in

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

(number of times 1 appears*1 + number of times 5 appears * 5 + ... )

Which is same as the reciprocal of

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

You can now factorize each in terms of products of roots of unity, split the reciprocal in terms of Partial Fractions (which is a one time step) and find the coefficient of x^N in each (which will be of the form Polynomial/(x-w)) and add them up.

You could do some DP in calculating the roots of unity.

Answer 2

You should not go from begining each time, but at max from were you came from at each depth. That mean that you have to pass two parameters, start and remaining 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 

or equivalent (it might be more readable)

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 3

Terminology: What you are looking for is the "integer partitions" into prescibed parts (you should replace "combinations" in the title). Ignoring the "dynamic programming" part of the question, a routine for your problem is given in the first section of chapter 16 ("Integer partitions", p.339ff) of the fxtbook, online at http://www.jjj.de/fxt/#fxtbook