ゼロから始める動的計画法 - コイン問題
問題設定
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やから8種類やな!
- 8 重 ル ー プ
- 処理重すぎて止まるコンソール
- というのは少々大げさで、総当たりでもプロジェクトオイラーは解けてしまいます
- 8重ループによる総当たり解答
- 組み合わせは1万を超えます
しかしこれでは競技プログラミングには勝てません、どうしましょう
動的計画法による解答
ここからは、もっと計算量の少ない方法を、YouTubeの動画から解説を引用して流れを追っていきたいと思います。計算量の少ない方法とは 動的計画法 - Wikipedia です。
問題を簡単にする
まず、合計金額が N = 5 となるように、コイン { 1, 2, 3 } を使って支払いの方法を数え上げるとしよう。普通に数え上げると、以下のように5通りになるはず。
- {1, 1, 1, 1, 1}
- {1, 1, 1, 2}
- {1, 1, 3}
- {2, 3}
- {2, 2, 1}
なぜ動的計画法か?
まずは2次元配列で
(1) コインの種別を行、合計値を列に取る集計表を考える
- 表の行は支払いに使えるコインの種別に関係しており、行の一番上からその行までのコインのみを使って支払いを行う
- コインの種別は、 C1 = 1, C2 = 2, C3 = 3 という記号で表すことにする
C\N | 0 | 1 | 2 | 3 | 4 | 5 |
---|---|---|---|---|---|---|
C1=1 | ||||||
C2=2 | ||||||
C3=3 |
(2) N = 0, の場合支払い方はすべて1通りしかない(0枚支払うということ、なんじゃそら)。ここまでは準備。
C\N | 0 | 1 | 2 | 3 | 4 | 5 |
---|---|---|---|---|---|---|
C1=1 | 1 | |||||
C2=2 | 1 | |||||
C3=3 | 1 |
(3) C1 のみ使える場合, 支払い方はすべて1通りしかない。合計金額がいくつであっても、1円で支払う方法は各自1通りしかない。
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が使える状態を考える, ここからが重要。それぞれ①〜⑤で印をつけた
- ここからは、対象の行の硬貨を1枚使うか使わないかをシミュレートする。
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枚使う方法 ⇛ 合計金額を超えてしまうので0通り
- C2を 0枚使う方法 ⇛ C1を使ってN=1を目指す方法なので、これは先程求めている1通り
- 合計1通り
(4)-② : N = 2
- C2を 1枚使う方法 ⇛ 1枚使えば合計金額ピッタリ、よって1通り
- C2を 0枚使う方法 ⇛ C1だけを使ってN=2を目指す方法なので、これは先程求めている1通り
- 合計2通り
(4)-③ : N = 3
- C2を 1枚使う方法 ⇛ 1枚使うと N=3-2=1、これはC1だけでN=1を目指す問題に化ける、よって1通り
- C2を 0枚使う方法 ⇛ C1だけを使ってN=3を目指す方法なので、これは先程求めている1通り
- 合計2通り
(4)-④ : N = 4
- C2を 1枚使う方法 ⇛ 1枚使うと N=4-2=2、これはC1,C2を使ってN=2を目指す問題に化ける、よって2通り
- C2を 0枚使う方法 ⇛ C1だけを使ってN=4を目指す方法なので、これは先程求めている1通り
- 合計3通り
(4)-⑤ : N = 5
- C2を 1枚使う方法 ⇛ 1枚使うと N=5-2=3、これはC1,C2を使ってN=3を目指す問題に化ける、よって2通り
- C2を 0枚使う方法 ⇛ C1だけを使ってN=5を目指す方法なので、これは先程求めている1通り
- 合計3通り
というわけで表が埋まる
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が使える状態を考える。それぞれ①〜⑤で印をつけた
- 同様にして、対象の行の硬貨を1枚使うか使わないかをシミュレートする。
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枚使う方法 ⇛ 合計金額を超えてしまうので0通り
- C3を 0枚使う方法 ⇛ C1,C2を使ってN=1を目指す方法なので、これは先程求めている1通り
- 合計1通り
(5)-② : N = 2
- C3を 1枚使う方法 ⇛ 合計金額を超えてしまうので0通り
- C3を 0枚使う方法 ⇛ C1,C2だけを使ってN=2を目指す方法なので、これは先程求めている2通り
- 合計2通り
(5)-③ : N = 3
- C3を 1枚使う方法 ⇛ 1枚使えば合計金額ピッタリ、よって1通り
- C3を 0枚使う方法 ⇛ C1,C2だけを使ってN=3を目指す方法なので、これは先程求めている2通り
- 合計3通り
(5)-④ : N = 4
- C3を 1枚使う方法 ⇛ 1枚使うと N=4-3=1、これはC1,C2を使ってN=1を目指す問題に化ける、よって1通り
- C3を 0枚使う方法 ⇛ C1,C2だけを使ってN=4を目指す方法なので、これは先程求めている3通り
- 合計4通り
(5)-⑤ : N = 5
- C3を 1枚使う方法 ⇛ 1枚使うと N=5-3=2、これはC1,C2を使ってN=2を目指す問題に化ける、よって2通り
- C3を 0枚使う方法 ⇛ C1,C2だけを使ってN=5を目指す方法なので、これは先程求めている3通り
- 合計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の行は階段状に数値が増加した。組み合わせの総数は配列の最大値となる。よって5通り。
Rubyのコードに落とし込む
- 表の行と列を舐めて全て見ていくのはfor文の2重ループで実現できる
- 処理としては、以下の2つに注目してもらいたい
- coins[i]を1枚使う方法
- dp[i][j - coins[i]] ← ここまで短縮されるとまるで意味不明。
- 要は、ある目指すべき合計値N(=j)からループ内で処理しているコインの金額を引いて、その時の計算済みの場合の数を見に行っている
- わからなければ、上に戻って手順の文章を読むと良いです
- coins[i]を0枚使う方法
- 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]を1枚使う方法 first = dp[i][j - coins[i]] # coins[i]を0枚使う方法 second = dp[i-1][j] puts "N = #{j}" puts "#{coins[i]} を1枚使う方法 => #{first}" puts "#{coins[i]} を0枚使う方法 => #{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