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 回答