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)。

これで、1の根の積に関してそれぞれを因数分解し、逆数を部分分数(これは 1 時間ステップです) に関して分割し、それぞれの x^N の係数を見つけることができます (多項式/( の形式になります)。 xw)) し、それらを合計します。

1 の根を計算する際に DP を実行できます。

于 2010-08-09T21:08:06.677 に答える
5

毎回最初から行くべきではありませんが、最大で各深さから来ました。つまり、開始と残りの合計の 2 つのパラメーターを渡す必要があります。

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 に答える