3

考虑一下你有一个价值的问题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 习语是什么?(不欢迎非优雅的解决方案,例如生成所有可能的解决方案和删除重复项)

4

3 回答 3

7

不确定任何 DP 习语,但您可以尝试使用Generating Functions

我们需要找到的是 x^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-x)(1-x^5)(1-x^10)(1-x^20)(1-x^50)(1-x^100)。

您现在可以根据单位根的乘积对每个进行因式分解,根据部分分数(这是一个时间步长)拆分倒数并找到每个中的 x^N 系数(其形式为多项式/( xw)) 并将它们相加。

你可以做一些 DP 来计算统一的根。

于 2010-08-09T21:08:06.677 回答
5

你不应该每次都从头开始,但在最大程度上你来自每个深度。这意味着您必须传递两个参数,开始和剩余总数。

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 
于 2010-08-09T21:23:23.537 回答
1

术语:您正在寻找的是“整数分区”到规定的部分(您应该替换标题中的“组合”)。忽略问题的“动态规划”部分,您的问题的例程在 fxtbook 的第 16 章(“整数分区”,p.339ff)的第一部分给出,在线 http://www.jjj.de /fxt/#fxtbook

于 2010-08-10T15:00:26.623 回答