18

変更作成の問題に対する適切な解決策を探していたところ、次のコード (Python) が見つかりました。

target = 200
coins = [1,2,5,10,20,50,100,200]
ways = [1]+[0]*target
for coin in coins:
    for i in range(coin,target+1):
        ways[i]+=ways[i-coin]
print(ways[target])

コードが文字通り何をするのかを理解するのに問題はありませんが、なぜそれが機能するのか理解できません。誰でも助けることができますか？

4

4 に答える 4

16

要素が 'a' または 'b' または 'c' (私たちのコイン) に等しく、合計が 'X' になるすべての可能なセットを取得するには、次のことができます。

  • 合計が Xa になるすべてのセットを取り、それぞれに余分な「a」を追加します。
  • 合計が Xb になるようなすべてのセットを取り、それぞれに余分な「b」を追加します。
  • 合計が Xc になるすべての集合を取り、それぞれに余分な 'c' を追加します。

したがって、X を取得できる方法の数は、Xa と Xb と Xc を取得できる方法の数の合計です。

ways[i]+=ways[i-coin]

残りは単純な繰り返しです。

追加のヒント: 最初に、1 つの方法 (空のセット) で合計ゼロを設定できます。

ways = [1]+[0]*target
于 2013-02-21T01:19:24.470 に答える
10

これは、動的計画法の古典的な例です。キャッシングを使用して、3+2 = 5 を 2 回カウントするという落とし穴を回避します (別の解として 2+3 が考えられるため)。再帰アルゴリズムはその落とし穴に陥ります。target = 5簡単な例 whereとに注目しましょうcoins = [1,2,3]。あなたが投稿したコードは次のとおりです。

  1. 3+2
  2. 3+1+1
  3. 2+2+1
  4. 1+2+1+1
  5. 1+1+1+1+1

再帰的なバージョンは次のようにカウントされます。

  1. 3+2
  2. 2+3
  3. 3+1+1
  4. 1+3+1
  5. 1+1+3
  6. 2+1+2
  7. 1+1+2
  8. 2+2+1
  9. 2+1+1+1
  10. 1+2+1+1
  11. 1+1+2+1
  12. 1+1+1+2
  13. 1+1+1+1+1

再帰コード:

coinsOptions = [1, 2, 3]
def numberOfWays(target):
    if (target < 0):
        return 0
    elif(target == 0):
        return 1
    else:
        return sum([numberOfWays(target - coin) for coin in coinsOptions])
print numberOfWays(5)

動的計画法:

target = 5
coins = [1,2,3]
ways = [1]+[0]*target
for coin in coins:
    for i in range(coin, target+1):
        ways[i]+=ways[i-coin]
print ways[target]
于 2013-02-21T01:38:10.813 に答える
4

コードの背後にある主なアイデアは次のとおりです。「各ステップには、与えられたコインの金額をways変更する方法があります」.i[1,...coin]

したがって、最初の反復では、 の額面のコインしかありません1。どのターゲットに対しても、これらのコインのみを使用して変更を加える方法が 1 つしかないことは明らかだと思います。このステップでは、ways配列は( からまで[1,...1]のすべてのターゲットに対して一方向のみ) のようになります。0target

2次のステップでは、前のコインのセットに の額面のコインを追加します。0これで、 からまでの各ターゲットに対していくつの変更の組み合わせがあるかを計算できますtarget。明らかに、組み合わせの数は、ターゲット >= 2(または一般的なケースで追加された新しいコイン) の場合にのみ増加します。したがって、ターゲットが等しい場合2、組み合わせの数はways[2](old)+になりますways[0](new)。i一般に、新しいコインが導入されるたびに、1以前の組み合わせの数に追加する必要があり、新しい組み合わせは 1 つのコインのみから構成されます。

target>の場合2、答えは「すべてのコインがそれより小さい金額のすべての組み合わせ」と「すべてのコインがそれ自体より小さい金額のすべての組み合わせ」の合計で構成targetさcoinれcoinますcoin。

ここでは 2 つの基本的な手順について説明しましたが、一般化するのは簡単だと思います。

target = 4と の計算ツリーを示しますcoins=[1,2]。

方法[4] 与えられたコイン=[1,2] =

方法[4] 与えられたコイン=[1] + 方法[2] 与えられたコイン=[1,2] =

1 + 方法[2] 与えられたコイン=[1] + 方法[0] 与えられたコイン=[1,2] =

1 + 1 + 1 = 3

したがって、変更を加えるには 3 つの方法があります[1,1,1,1], [1,1,2], [2,2]。

上記のコードは、再帰的なソリューションと完全に同等です。再帰的な解決策を理解していれば、上記の解決策を理解しているに違いありません。

于 2013-02-21T01:39:02.780 に答える