貪欲法

GPT-4.icon

貪欲法（Greedy Algorithm）は、最適化問題に対するアルゴリズムの一つで、各ステップで局所的に最適な選択をすることで、最終的な解決策を導き出すアプローチです。この方法は、各ステップでの最適な選択が全体としても最適である場合に特に有効です。しかし、すべての問題に対して最適な解を得られるわけではありません。

Haskellでの具体例としては、硬貨の問題を考えてみましょう。この問題では、特定の金額を、できるだけ少ない数の硬貨で支払う方法を見つけることが目的です。日本の硬貨を使用する場合、1円、5円、10円、50円、100円、500円の硬貨があります。

以下に、Haskellでの貪欲法を用いた解法の一例を示します。

code:hs

-- 硬貨の種類を定義

-- 貪欲法による硬貨の組み合わせを求める関数

makeChange _ [] = []

makeChange amount (c:cs)

| amount >= c = c : makeChange (amount - c) (c:cs)

| otherwise = makeChange amount cs

-- 例: 123円を支払うための硬貨の組み合わせを求める

main :: IO ()

main = print $ makeChange 123 coins

このコードでは、最も価値が高い硬貨から順に、支払う金額を超えない範囲でできるだけ多くの硬貨を使用します。この方法は日本の硬貨システムのように「大きい硬貨の額面が小さい硬貨の額面の倍数である」場合に最適な解を導きますが、異なる硬貨システムでは必ずしも最適な解が得られるとは限りません。

関連