サーチ…


合計を得る方法の数

異なる金種のコインと合計を考えれば、合計を得るためにこれらのコインをどのように組み合わせることができますか? coins = {1, 2, 3}total = 5場合、 5つの方法で合計を得ることができます。

  • 1 1 1 1 1
  • 1 1 1 2
  • 1 1 3
  • 1 2 2
  • 2 3

この問題は、ナップザック問題と密接に関連しています。唯一の違いは、コインの無制限供給があることです。この問題を解決するためにダイナミックプログラミングを使用します。

私たちは2D配列dp [n] [total + 1]を使用しますここで、 nは私たちが所有するコインの異なる金種の数です。この例では、 dp [3] [6]が必要です。ここで、 dp [i] [j]は、 コイン[0]からコイン[i]までのコインがあれば、 jを得る方法の数を示します。例えば、 dp [1] [2]は、 コイン[0]コイン[1]を持っていれば、 2を作ることができる方法を格納します。さぁ、始めよう:

我々は、コインの唯一の1宗派があった場合、DPの場合は[0] [0]、我々はそれはコインが[0] = 1、我々は0をどのように多くの方法を得ることができるであり、自分自身を求めていますか?答えは1つの方法です。これは、コインを一切取らない場合です。移動すると、 dp [0] [1]コイン[0]だけを持っていれば1を得ることができます。答えは再び1です。同様に、 dp [0] [2]dp [0] [3]dp [0] [4]dp [0] [5]1になります。私たちの配列は次のようになります:

     +---+---+---+---+---+---+---+
(den)|   | 0 | 1 | 2 | 3 | 4 | 5 |
     +---+---+---+---+---+---+---+
 (1) | 0 | 1 | 1 | 1 | 1 | 1 | 1 |
     +---+---+---+---+---+---+---+
 (2) | 1 |   |   |   |   |   |   |
     +---+---+---+---+---+---+---+
 (3) | 2 |   |   |   |   |   |   |
     +---+---+---+---+---+---+---+

私たちは2つの宗派のコインを持っていた場合、DPの場合は、[1] [0]、我々はコインが[0] = 1コイン[1] = 2、どのように多くの点で、我々は0を作ることができる持っていた場合には、自分自身を求めていますか?答えは1です 。これはコインを一切取ることではありません。 dp [1] [1]では、 コイン[1] = 2が現在の合計よりも大きいので、 2は合計を得ることに寄与しません。したがって、 2を除外し、 コインを使用して合計を得る方法の数を数えます[0] 。しかし、この値は既にdp [0] [1]に保存されています!だから、私たちは上からその価値を取ります。私たちの最初の公式:

if coins[i] > j
    dp[i][j] := dp[i-1][j]
end if

dp [1] [2]の場合、 12の名義のコインがあれば、 2を得る方法は何通りありますか?我々は、ここで、i [i]は[2-コイン] [1] [0] [2]、再び我々はDPに格納されている21金種を取ることができ、DPで表される1の金種の硬貨を使用して2を作ることができます= 1 。どうして?次の例を見ると明らかです。 dp [1] [3]の場合、金種12のコインがあれば、どれだけ多くの方法で3を得ることができますか?我々は、 dp [0] [3]に格納されている金種1のコインを1ウェイで使用して3を作ることができます。今度は2の 1つの宗派をとると、合計を得るには3 - 2 = 1が必要になります。いくつかの方法は、DPに格納されている金種1及び2のコインを使用して1を取得する[1] [1]、DP [I]、[J-コイン[I]、I = 1、のように書くことができます。これが前の値をこのように書いた理由です。私たちの2番目の最終的な式は次のようになります。

if coins[i] <= j
    dp[i][j] := dp[i-1][j] + dp[i][j-coins[i]]
end if

これは、 dp配列全体を満たすために必要な2つの数式です。配列を埋めると、次のようになります:

     +---+---+---+---+---+---+---+
(den)|   | 0 | 1 | 2 | 3 | 4 | 5 |
     +---+---+---+---+---+---+---+
 (1) | 0 | 1 | 1 | 1 | 1 | 1 | 1 |
     +---+---+---+---+---+---+---+
 (2) | 1 | 1 | 1 | 2 | 2 | 3 | 3 |
     +---+---+---+---+---+---+---+
 (3) | 2 | 1 | 1 | 2 | 3 | 4 | 5 |
     +---+---+---+---+---+---+---+

dp [2] [5]には必要な答えが含まれています。アルゴリズム:

Procedure CoinChange(coins, total):
n := coins.length
dp[n][total + 1]
for i from 0 to n
    dp[i][0] := 1
end for
for i from 0 to n
    for j from 1 to (total + 1)
        if coins[i] > j
            dp[i][j] := dp[i-1][j]
        else
            dp[i][j] := dp[i-1][j] + dp[i][j-coins[i]]
        end if
    end for
end for
Return dp[n-1][total]

このアルゴリズムの時間複雑度はO(n * total) 。ここでnは、私たちが持っている硬貨の金種の数です。

合計を得るための最小コイン数

異なる金種のコインと合計を考えると、最小のコインを使用すれば合計を得るために何本のコインを組み合わせる必要がありますか? coins = {1, 5, 6, 8}total = 11場合、 {5, 6}コイン2枚で合計を得ることができます。これは確かに11を得るために必要なコインの最小数です。また、コインの無制限供給も想定しています。この問題を解決するためにダイナミックプログラミングを使用します。

私たちは2D配列dp [n] [total + 1]を使用しますここで、 nは私たちが所有するコインの異なる金種の数です。この例では、 dp [4] [12]が必要です。ここで、 dp [i] [j]は、 コイン[0]からコイン[i]までのコインがあれば、 jを得るために必要なコインの最小数を示します。例えば、 dp [1] [2]は、 コイン[0]コイン[1]を持っていれば、 2を作るのに使うコインの最小枚数を格納します。さぁ、始めよう:

最初は、 0列目で、コインを一切取らないことで0にすることができます。したがって、 0番目の列の値はすべて0になりますDPのために[1]、我々はコインの唯一の1つの宗派があった場合、それはコインである自分自身を求めている[0] [0] = 1、1取得するために必要なコインの最小数は何ですか?答えは1です。 dp [0] [2]に対して、 1つしかなかった場合、 2を得るために必要なコインの最小数はどれくらいですか?答えは2です。同様に、 dp [0] [3] = 3dp [0] [4] = 4などとなります。ここで言及しなければならないことの一つは、金種1のコインがなければ、 1コインのみを使用して合計を達成できない場合があることです。簡単にするために、例では1をとります。最初の反復の後、私たちのdp配列は次のようになります:

        +---+---+---+---+---+---+---+---+---+---+---+---+---+
 (denom)|   | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10| 11|
        +---+---+---+---+---+---+---+---+---+---+---+---+---+
    (1) | 0 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10| 11|
        +---+---+---+---+---+---+---+---+---+---+---+---+---+
    (5) | 1 | 0 |   |   |   |   |   |   |   |   |   |   |   |
        +---+---+---+---+---+---+---+---+---+---+---+---+---+
    (6) | 2 | 0 |   |   |   |   |   |   |   |   |   |   |   |
        +---+---+---+---+---+---+---+---+---+---+---+---+---+
    (8) | 3 | 0 |   |   |   |   |   |   |   |   |   |   |   |
        +---+---+---+---+---+---+---+---+---+---+---+---+---+

私たちはコインを持っていた場合は、[1] [1]、我々は自分自身をDPのために、上の移動を求めている[0] = 1コイン[1] = 5、1取得するために必要なコインの最小数は何ですか? コイン[1]は現在の合計よりも大きいので、計算には影響しません。私たちはコイン[5]を除外し、 コイン[0]だけを使って1を得る必要があります。この値はdp [0] [1]に格納されます。だから私たちはその価値観を上から取ります。私たちの最初の公式は:

if coins[i] > j
    dp[i][j] := dp[i-1][j]

この条件は、合計がdp [1] [5]5になるまで真となります。その場合、次の2つの方法で5を作成できます。

  • 私たちはdp [0] [5] (上から)に格納されている5 銭のコイン[0]を受け取ります。
  • 我々は、 コイン1金種を取る[1]及び(5から5) 硬貨の金種= 0 [0]。

これらの2つの最小値を選択します。したがって、 dp [1] [5] = min( dp [0] [5]1 + dp [1] [0] )= 1 。なぜ我々はここでコインの 0金種について述べましたか[0]ここで私たちの次の立場で明らかになります。

dp [1] [6]の場合、 6つの方法で6つを作ることができます:

  • 私たちは6 銭のコイン[0]を取ります。これは上部に保管されています。
  • 私たちは5の 1つの宗派を取ることができます、合計を得るために6 - 5 = 1が必要です。方法の最小数は、DP [1] [1]、DPのように書くことができる[I]、[J-コイン[I]、ここで、i = 1に格納されている金種15のコインを使用して1を取得します。これが私たちが以前の価値をそのように書いた理由です。

我々は、これらの2つの方法の最小限を取る。だから私たちの2番目の式は次のようになります

if coins[i] >= j
    dp[i][j] := min(dp[i-1][j], dp[i][j-coins[i]])

これらの2つの式を使用して、テーブル全体を埋めることができます。私たちの最終結果は次のようになります:

        +---+---+---+---+---+---+---+---+---+---+---+---+---+
 (denom)|   | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10| 11|
        +---+---+---+---+---+---+---+---+---+---+---+---+---+
    (1) | 0 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10| 11|
        +---+---+---+---+---+---+---+---+---+---+---+---+---+
    (5) | 1 | 0 | 1 | 2 | 3 | 4 | 1 | 2 | 3 | 4 | 5 | 2 | 3 |
        +---+---+---+---+---+---+---+---+---+---+---+---+---+
    (6) | 2 | 0 | 1 | 2 | 3 | 4 | 1 | 1 | 2 | 3 | 4 | 2 | 2 |
        +---+---+---+---+---+---+---+---+---+---+---+---+---+
    (8) | 3 | 0 | 1 | 2 | 3 | 4 | 1 | 1 | 2 | 1 | 2 | 2 | 2 |
        +---+---+---+---+---+---+---+---+---+---+---+---+---+

必要な結果はdp [3] [11]に格納されます。手順は次のとおりです。

Procedure coinChange(coins, total):
n := coins.length
dp[n][total + 1]
for i from 0 to n
    dp[i][0] := 0
end for
for i from 1 to (total + 1)
    dp[0][i] := i
end for
for i from 1 to n
    for j from 1 to (total + 1)
        if coins[i] > j
            dp[i][j] := dp[i-1][j] 
        else
            dp[i][j] := min(dp[i-1][j], dp[i][j-coins[i]])
        end if
    end for
end for
Return dp[n-1][total]

このアルゴリズムの実行時の複雑さは次のとおりです。O(n * total)ここで、 nはコインの金種の数です。

必要な硬貨を印刷するには、以下を確認する必要があります。

  • 値がトップから来た場合、現在のコインは含まれません。
  • 値が左から来た場合、現在のコインが含まれます。

アルゴリズムは次のようになります。

Procedure printChange(coins, dp, total):
i := coins.length - 1
j := total
min := dp[i][j]
while j is not equal to 0
    if dp[i-1][j] is equal to min
        i := i - 1
    else
        Print(coins[i])
        j := j - coins[i]
    end if
end while

この例では、方向は次のようになります。

方向配列

値は6、5になります。



Modified text is an extract of the original Stack Overflow Documentation
ライセンスを受けた CC BY-SA 3.0
所属していない Stack Overflow