概要¶
貪欲法（Greedy Algorithm） は、各ステップで「その時点で最も良く見える選択」を繰り返すことで解を構築するアルゴリズム設計手法である。
基本的な考え方¶
問題をステップに分割し、各ステップで局所的に最適な選択をする
一度した選択は覆さない（後戻りしない）
全体の最適解を保証するには、問題が以下の2つの性質を満たす必要がある
| 性質 | 説明 |
|---|---|
| 貪欲選択性（Greedy Choice Property） | 局所最適な選択を重ねることで大域最適解に到達できる |
| 最適部分構造（Optimal Substructure） | 問題の最適解が部分問題の最適解を含む |
利点と欠点¶
利点
実装がシンプルで理解しやすい
多くの場合、動的計画法より高速
欠点
適用できる問題が限られる（すべての最適化問題に使えるわけではない）
局所最適解が大域最適解にならないケースがある（例：一般的なコイン問題、0/1 ナップサック問題）
coins = [500, 100, 50, 10, 5, 1] # 硬貨の種類
X = 873 # 例：873円を払いたい
total = 0
for coin in coins:
count = X // coin # その硬貨を何枚使えるか
if count > 0:
total += count
X %= coin # 残りの金額を更新
print(total)10
def activity_selection(jobs: list[tuple[int, int]]) -> list[tuple[int, int]]:
"""
区間スケジューリング: 重複なしで選べる仕事の最大集合を返す
Parameters
----------
jobs : list of (start, end)
"""
sorted_jobs = sorted(jobs, key=lambda x: x[1]) # 終了時刻でソート
selected = []
last_end = -1
for start, end in sorted_jobs:
if start >= last_end:
selected.append((start, end))
last_end = end
return selected
jobs = [(1, 4), (3, 5), (0, 6), (5, 7), (3, 9), (5, 9), (6, 10), (8, 11), (8, 12), (2, 14)]
result = activity_selection(jobs)
print(f"選択された仕事 ({len(result)}件):")
for s, e in result:
print(f" [{s}, {e})")例3: 分数ナップサック問題¶
Q. 容量 のナップサックに、重さ ・価値 のアイテムを詰めるとき価値を最大化するには？ アイテムを 分割して詰めてよい（分数ナップサック）場合は貪欲法で最適解が得られる。
貪欲な選択: 単位重量あたりの価値（）が高いアイテムから詰める。
※ アイテムの分割が許されない 0/1 ナップサック問題 では貪欲法では最適解が保証されない（動的計画法が必要）。
def fractional_knapsack(capacity: float, items: list[tuple[float, float]]) -> float:
"""
分数ナップサック問題
Parameters
----------
capacity : float
ナップサックの容量
items : list of (weight, value)
Returns
-------
float
最大価値
"""
# 単位重量あたりの価値で降順ソート
sorted_items = sorted(items, key=lambda x: x[1] / x[0], reverse=True)
total_value = 0.0
remaining = capacity
for weight, value in sorted_items:
if remaining <= 0:
break
take = min(weight, remaining)
total_value += value * (take / weight)
remaining -= take
return total_value
capacity = 50
items = [
(10, 60), # 重さ10, 価値60 → 単価6.0
(20, 100), # 重さ20, 価値100 → 単価5.0
(30, 120), # 重さ30, 価値120 → 単価4.0
]
max_value = fractional_knapsack(capacity, items)
print(f"最大価値: {max_value}")