アルゴリズム・データ構造 プログラミング

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

アルゴリズム解説_貪欲法

貪欲法とは

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

貪欲法の手順

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

coins01

計算手順

  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枚を計算することが出来ました。

278yen

サンプルコード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円, 5円, 1円]の硬貨を使ってお釣りが出ないように支払う最少の硬貨枚数を計算をしてみます。

coins02

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枚が正解です。

【間違い】

240yen01

【正解】

240yen02

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

サンプルコード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 相当)

【PR】Ruby学習でお世話になった本




【PR】アルゴリズム学習でお世話になった本


アルゴリズム関連の技術書は大抵C/C++で書かれていますが、ある程度プログラムが出来れば、処理の流れは理解することが出来ます。






通称: 螺旋本。C++で解説されています。AOJ(Aizu Online Judge)を運営している会津大学の渡辺准教授が書いた本です。データ構造や計算量の内容から丁寧に書いてありますのでアルゴリズム学習の最初の参考書としてオススメです。







通称: 蟻本。C++で解説されています。競技プログラミング中級者の定番書と言われていて、競技プログラミングで利用できる色々なアルゴリズムを学ぶことが出来ます。かなり高度な内容も含まれているので1冊分を完全に理解するのにはかなりの時間がかかりそうですが、手元に置いて何度も読み返しています。







通称: チーター本。C#, C++, JAVAでTopcoderの問題を解説しています。初心者~中級者向けに書かれているので解説が非常に丁寧です。







Python3でアルゴリズムを解説している本です。講義スタイルの本で、図やフローチャートを使ってアルゴリズムとデータ構造についてしっかりと説明されています。代わりにコードは少なめです。Pythonコードが読めなくても十分理解できると思います。


-アルゴリズム・データ構造, プログラミング
-

© 2024 じゃいごテック