ゼロから始める動的計画法 - コイン問題 - なんとな～くしあわせ？の日記

問題設定
- Project Euler Problem 31
- 考察
動的計画法による解答
Rubyのコードに落とし込む
プロジェクトオイラー用に微調整

問題設定

Project Euler Problem 31

ターゲットとする問題は以下

Project Euler - Problem 31 「硬貨の和」

イギリスでは硬貨はポンド£とペンスpがあり，一般的に流通している硬貨は以下の8種類である. 1p, 2p, 5p, 10p, 20p, 50p, £1 (100p) and £2 (200p).
以下の方法で£2を作ることが可能である．
1×£1 + 1×50p + 2×20p + 1×5p + 1×2p + 3×1p
これらの硬貨を使って£2を作る方法は何通りあるか?

考察

文系大学生の気持ちでいろいろ考えてみる

枚数をちょっと考えてみる
- 200ポンドを1ペンス硬貨で作る⇛1ペンス×200枚で達成、最も枚数が多そう
- 200ポンドを1ポンド硬貨で作る⇛1ポンド×1枚で達成、最も枚数が少なそう
- 場合の数の合計がパない

せや！総当たりや
- 硬貨の価値が最も高いものから順にループを組み、合計値が200になったものを記録する
- さて、コインの種別は何個やったかな？、1, 2, 5, 10, 20, 50, 100, 200やから８種類やな！
- ８　重　ル　ー　プ
- 処理重すぎて止まるコンソール

というのは少々大げさで、総当たりでもプロジェクトオイラーは解けてしまいます
- ８重ループによる総当たり解答
- 組み合わせは１万を超えます

しかしこれでは競技プログラミングには勝てません、どうしましょう

動的計画法による解答

ここからは、もっと計算量の少ない方法を、YouTubeの動画から解説を引用して流れを追っていきたいと思います。計算量の少ない方法とは動的計画法 - Wikipedia です。

www.youtube.com

問題を簡単にする

まず、合計金額が N = 5 となるように、コイン { 1, 2, 3 } を使って支払いの方法を数え上げるとしよう。普通に数え上げると、以下のように５通りになるはず。

{1, 1, 1, 1, 1}
{1, 1, 1, 2}
{1, 1, 3}
{2, 3}
{2, 2, 1}

なぜ動的計画法か？

問題が入れ子構造になっているので、動的計画法を使うことができる
- 例えば、コインの１枚めに1を使うとすれば、残りN=5-1=4 の問題に化ける
- N=4の問題を予め解いておけば、数え上げが楽になるというわけだ

まずは２次元配列で

(1) コインの種別を行、合計値を列に取る集計表を考える

表の行は支払いに使えるコインの種別に関係しており、行の一番上からその行までのコインのみを使って支払いを行う

コインの種別は、 C1 = 1, C2 = 2, C3 = 3 という記号で表すことにする

C\N	0	1	2	3	4	5
C1=1
C2=2
C3=3

(2) N = 0, の場合支払い方はすべて１通りしかない（０枚支払うということ、なんじゃそら）。ここまでは準備。

C\N	0	1	2	3	4	5
C1=1	1
C2=2	1
C3=3	1

(3) C1 のみ使える場合, 支払い方はすべて１通りしかない。合計金額がいくつであっても、１円で支払う方法は各自１通りしかない。

C\N	0	1	2	3	4	5
C1=1	1	1	1	1	1	1
C2=2	1
C3=3	1

(4) C1とC2が使える状態を考える, ここからが重要。それぞれ①〜⑤で印をつけた

ここからは、対象の行の硬貨を１枚使うか使わないかをシミュレートする。

C\N	0	1	2	3	4	5
C1=1	1	1	1	1	1	1
C2=2	1	①	②	③	④	⑤
C3=3	1

(4)-① : N = 1

C2を 1枚使う方法 ⇛ 合計金額を超えてしまうので０通り
C2を 0枚使う方法 ⇛ C1を使ってN=1を目指す方法なので、これは先程求めている１通り
合計１通り

(4)-② : N = 2

C2を 1枚使う方法 ⇛ １枚使えば合計金額ピッタリ、よって１通り
C2を 0枚使う方法 ⇛ C1だけを使ってN=2を目指す方法なので、これは先程求めている１通り
合計２通り

(4)-③ : N = 3

C2を 1枚使う方法 ⇛ １枚使うと N=3-2=1、これはC1だけでN=1を目指す問題に化ける、よって１通り
C2を 0枚使う方法 ⇛ C1だけを使ってN=3を目指す方法なので、これは先程求めている１通り
合計２通り

(4)-④ : N = 4

C2を 1枚使う方法 ⇛ １枚使うと N=4-2=2、これはC1,C2を使ってN=2を目指す問題に化ける、よって２通り
C2を 0枚使う方法 ⇛ C1だけを使ってN=4を目指す方法なので、これは先程求めている１通り
合計３通り

(4)-⑤ : N = 5

C2を 1枚使う方法 ⇛ １枚使うと N=5-2=3、これはC1,C2を使ってN=3を目指す問題に化ける、よって２通り
C2を 0枚使う方法 ⇛ C1だけを使ってN=5を目指す方法なので、これは先程求めている１通り
合計３通り

というわけで表が埋まる

C\N	0	1	2	3	4	5
C1=1	1	1	1	1	1	1
C2=2	1	1	2	2	3	3
C3=3	1

(5) C1,C2,C3が使える状態を考える。それぞれ①〜⑤で印をつけた

同様にして、対象の行の硬貨を１枚使うか使わないかをシミュレートする。

C\N	0	1	2	3	4	5
C1=1	1	1	1	1	1	1
C2=2	1	1	2	2	3	3
C3=3	1	①	②	③	④	⑤

(5)-① : N = 1

C3を 1枚使う方法 ⇛ 合計金額を超えてしまうので０通り
C3を 0枚使う方法 ⇛ C1,C2を使ってN=1を目指す方法なので、これは先程求めている１通り
合計１通り

(5)-② : N = 2

C3を 1枚使う方法 ⇛ 合計金額を超えてしまうので０通り
C3を 0枚使う方法 ⇛ C1,C2だけを使ってN=2を目指す方法なので、これは先程求めている２通り
合計２通り

(5)-③ : N = 3

C3を 1枚使う方法 ⇛ １枚使えば合計金額ピッタリ、よって１通り
C3を 0枚使う方法 ⇛ C1,C2だけを使ってN=3を目指す方法なので、これは先程求めている２通り
合計３通り

(5)-④ : N = 4

C3を 1枚使う方法 ⇛ １枚使うと N=4-3=1、これはC1,C2を使ってN=1を目指す問題に化ける、よって１通り
C3を 0枚使う方法 ⇛ C1,C2だけを使ってN=4を目指す方法なので、これは先程求めている３通り
合計４通り

(5)-⑤ : N = 5

C3を 1枚使う方法 ⇛ １枚使うと N=5-3=2、これはC1,C2を使ってN=2を目指す問題に化ける、よって２通り
C3を 0枚使う方法 ⇛ C1,C2だけを使ってN=5を目指す方法なので、これは先程求めている３通り
合計５通り

というわけで表が埋まる

C\N	0	1	2	3	4	5
C1=1	1	1	1	1	1	1
C2=2	1	1	2	2	3	3
C3=3	1	1	2	3	4	5

たまたまC3の行は階段状に数値が増加した。組み合わせの総数は配列の最大値となる。よって５通り。

Rubyのコードに落とし込む

表の行と列を舐めて全て見ていくのはfor文の２重ループで実現できる
処理としては、以下の２つに注目してもらいたい
coins[i]を１枚使う方法
- dp[i][j - coins[i]] ← ここまで短縮されるとまるで意味不明。
- 要は、ある目指すべき合計値N(=j)からループ内で処理しているコインの金額を引いて、その時の計算済みの場合の数を見に行っている
- わからなければ、上に戻って手順の文章を読むと良いです
coins[i]を０枚使う方法
- dp[i-1][j]
- ここは、ループ内で処理しているコインを使わずにある目指すべき合計値N(=j)を達成することのできる、計算済みの場合の数を見に行っている

COINS = [1, 2, 3]

def coin(amount,kind,coins)

  coins = [0].concat(coins)
  dp = Array.new(kind+1).map{Array.new(amount+1, 0)}

  dp.each{|row| row[0] = 1}

  for i in 1..kind
    for j in 1..amount
      # coins[i]を１枚使う方法
      first = dp[i][j - coins[i]]
      # coins[i]を０枚使う方法
      second = dp[i-1][j]

      puts "N = #{j}"
      puts "#{coins[i]} を１枚使う方法 => #{first}"
      puts "#{coins[i]} を０枚使う方法 => #{second}"
      dp[i][j] = first + second
    end
  end
  dp
end

N,M = 5,COINS.length
dp = coin(N,M,COINS)

puts dp.max.max

プロジェクトオイラー用に微調整

COINS = [1, 2, 5, 10, 20, 50, 100, 200]

def coin(amount,kind,coins)

  coins = [0].concat(coins)
  dp = Array.new(kind+1).map{Array.new(amount+1, 0)}
  dp.each{|row| row[0] = 1}

  for i in 1..kind
    for j in 1..amount
      dp[i][j] = dp[i][j - coins[i]] + dp[i-1][j]
    end
  end
  dp
end

N,M = 200,COINS.length
dp = coin(N,M,COINS)
p dp.max.max