[アルゴリズム(Ruby)]貪欲法の解説

貪欲法とは

貪欲法(greedy algorithm)は、欲張り法とも呼ばれ、問題を段階に分けたときに、各段階においての最適解を選択することを繰り返す方法です。
後のことを考えず、その場その場での最適解を選択していくため、問題によっては正解が求められない場合もありますので注意が必要です。

貪欲法の手順

例えば、ある商品の価格278円を[100円, 50円, 10円, ５円, １円]の硬貨を使ってお釣りが出ないように支払う最少の硬貨枚数を貪欲法で計算してみます。（価値が高い硬貨から順に考えるところがポイントです。）

計算手順

1.  278円に対して、100円が何枚使えるか？ → 278 ÷ 100 = 2 ・・・あまり 78円
2. 78円に対して、50円が何枚使えるか？ → 78 ÷ 50 = 1 ・・・あまり 28円
3. 28円に対して、10円が何枚使えるか？ → 28 ÷ 10 = 2 ・・・あまり 8円
4. 8円に対して、5円が何枚使えるか？ → 8 ÷ 5 = 1 ・・・あまり 3円
5. 3円に対して、1円が何枚使えるか？ → 3 ÷ 1 = 3 ・・・（あまり 0円）

これで、278円に対する、お釣りが出ない支払いの最少の硬貨枚数(2+1+2+1+3=9)9枚を計算することが出来ました。

サンプルコード1

上記の計算手順をそのまま実装してみます。

# 硬貨の種類
coin100 = 100
coin50 = 50
coin10 = 10
coin5 = 5
coin1 = 1
price = 278

bop = price
total_coins = 0
# 1. 100 円が何枚か
num_of_coins = bop / coin100
bop -= coin100 * num_of_coins
total_coins += num_of_coins

# 2. 50 円が何枚か
num_of_coins = bop / coin50
bop -= coin50 * num_of_coins
total_coins += num_of_coins

# 3. 10 円が何枚か
num_of_coins = bop / coin10
bop -= coin10 * num_of_coins
total_coins += num_of_coins

# 4. 5 円が何枚か
num_of_coins = bop / coin5
bop -= coin5 * num_of_coins
total_coins += num_of_coins

# 5. 1 円が何枚か
num_of_coins = bop / coin1
bop -= coin1 * num_of_coins
total_coins += num_of_coins

puts <<"EOS"
#{[coin100, coin50, coin10, coin5, coin1]} の硬貨を使って
#{price} 円を最少の硬貨枚数で支払うには
硬貨が #{total_coins} 枚必要
EOS

# > [100, 50, 10, 5, 1] の硬貨を使って
# > 278 円を最少の硬貨枚数で支払うには
# > 硬貨が 9 枚必要

サンプルコード2

サンプルコード1で同じ処理を繰り返している部分をまとめてみます。

coins = [100, 50, 10, 5, 1]
price = 278

bop = price
total_coins = 0
# coins の先頭から順に何枚使うか調べる
coins.each do |coin|
  num_of_coins = bop / coin
  bop -= coin * num_of_coins
  total_coins += num_of_coins
end

puts <<"EOS"
#{coins} の硬貨を使って
#{price} 円を最少の硬貨枚数で支払うには
硬貨が #{total_coins} 枚必要
EOS

# > [100, 50, 10, 5, 1] の硬貨を使って
# > 278 円を最少の硬貨枚数で支払うには
# > 硬貨が 9 枚必要

貪欲法で最適解が求められないケース

最初に説明した通り、問題によっては貪欲法では正解が求められない場合があります。

ある商品の価格240円を[100円, 80円, 10円, ５円, １円]の硬貨を使ってお釣りが出ないように支払う最少の硬貨枚数を計算をしてみます。

1. 240円に対して、100円が何枚使えるか？ → 240 ÷ 100 = 2 ・・・あまり 40円

2. 40円に対して、80円が何枚使えるか？ → 40 ÷ 80 = 0 ・・・あまり 40円

3. 40円に対して、10円が何枚使えるか？ → 40 ÷ 10 = 4 ・・・あまり 0円

4. 0円に対して、5円が何枚使えるか？ → 0 ÷ 5 = 0 ・・・あまり 0円

5. 0円に対して、1円が何枚使えるか？ → 0 ÷ 1 = 0 ・・・あまり 0円

240円に対して、お釣りが出ない支払いの最少の硬貨枚数は(2+0+4+0+0=6)6枚となります。

しかし、この問題では「80円を3枚」使った時の3枚が正解です。

このように、目先ではなく全体を見たうえで最適解を求める必要がある場合は別のアルゴリズムを選択する必要があります。

サンプルコード1 【貪欲法では間違いとなる】

貪欲法で実装すると間違った答え（6枚）が出力されることを確認してみます。

coins = [100, 80, 10, 5, 1]
price = 240

bop = price
total_coins = 0
# coins の先頭から順に何枚使うか調べる
coins.each do |coin|
  num_of_coins = bop / coin
  bop -= coin * num_of_coins
  total_coins += num_of_coins
end

puts <<"EOS"
#{coins} の硬貨を使って
#{price} 円を最少の硬貨枚数で支払うには
硬貨が #{total_coins} 枚必要
EOS

# > [100, 80, 10, 5, 1] の硬貨を使って
# > 240 円を最少の硬貨枚数で支払うには
# > 硬貨が 6 枚必要

サンプルコード2 【動的計画法で計算する】

手持ちの硬貨で作れる240円以下の最少硬貨枚数を一通り調べた後に、240円の最少硬貨枚数を出力します。
（動的計画法については別の記事で解説していますので、よかったら参考にしてみて下さい。）
[アルゴリズム(Ruby)]分割統治法・動的計画法（マージソート・フィボナッチ数・部分和問題を例に解説）

coins = [100, 80, 10, 5, 1]
price = 240

len = coins.length
dp = Array.new(len + 1) { Array.new(price + 1, Float::INFINITY) }
dp[0][0] = 0

1.upto(len) do |i|
  coin = coins[i - 1]
  0.upto(price) do |j|
    if j < coin
      dp[i][j] = dp[i - 1][j]
    else
      dp[i][j] = [dp[i][j - coin] + 1, dp[i - 1][j]].min
    end
  end
end

puts <<"EOS"
#{coins} の硬貨を使って
#{price} 円を最少の硬貨枚数で支払うには
硬貨が #{dp[-1][-1]} 枚必要
EOS

# > [100, 80, 10, 5, 1] の硬貨を使って
# > 240 円を最少の硬貨枚数で支払うには
# > 硬貨が 3 枚必要

今回のまとめ

• 貪欲法は問題を段階に分けて、各段階での最適解を選択していく。
• 貪欲法は先の段階を考慮する必要がある問題では最適解が求められない場合がある。

「貪欲法」で解いているので、こちらの記事も良かったら参考にしてください！
↓↓↓

[Ruby]paiza リアルイベント問題セット 雪だるま作り (paizaランク A 相当)