トップ 差分 一覧 ソース 検索 ヘルプ RSS ログイン

動的計画法 - コイン問題

[アルゴリズム,DP]

動的計画法 - コイン問題

  問題設定

問題
額面がc1, c2,..., cm 円の m 種類のコインを使って、 n 円を支払うときの、コインの最小の枚数を求めて下さい。各額面のコインは何度でも使用することができます。

Rubyコード

  • コインの最小の枚数を求める
# coding: utf-8
lines = <<'EOS'
100 6
1 72 93 34 24 37
EOS

#lines = $stdin.read
array = lines.split("\n")

INF = 1 << 25

def coin(amount,kind,coins)
  dp = Array.new(amount+1, INF)
  dp[0] = 0
  for i in 0...kind
    for j in coins[i]..amount
      dp[j] = [dp[j], dp[j - coins[i]] + 1].min
    end
  end
  dp
end

N,M = array[0].split(" ").map(&:to_i)
coins = array[1].split(" ").map(&:to_i)

dp = coin(N,M,coins)
puts dp[N]

コイン問題 - 類題

  すべての組み合わせの数を求める

問題
額面がc1, c2,..., cm 円の m 種類のコインを使って、 n 円を支払うときの方法は何通りあるか?

理解のために

簡単な例から

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

なぜ動的計画法か?

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

まずは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コード

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

1次元配列でできるじゃない

Rubyコード

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

def coin(amount,kind,coins)
  dp = Array.new(amount+1, 0)
  dp[0] = 1
  for i in 0...kind
    for j in coins[i]..amount
      dp[j] += dp[j - coins[i]]
    end
  end
  dp
end

N,M = 200,COINS.length
dp = coin(N,M,COINS)
p dp
puts dp[N]

  すべての組み合わせの数と組み合わせのパターンを求める

問題
額面がc1, c2,..., cm 円の m 種類のコインを使って、 n 円を支払うときの方法は何通りあるか? また、そのパターンをすべて出力せよ。
お名前: コメント: