---
title: Greedy Algorithm
tags: Algorithm
---

# Greedy Algorithm

## 什麼是 Greedy Algorithm（貪婪演算法）
持續找到「目前」最佳解，直到完成「全域」最佳解。
> 每一步都貪婪！

貪婪演算法永遠選擇「現在」看起來最佳的解法。

### Key Idea
- 一次做出一個選擇
- 永不回頭
- 期望最好的結果

## Warm-up: Walking in Manhattan
> Walk in a direction that reduces distance to the destination.


:::warning
Greedy does not always work
:::

## 設計與分析
### 設計
1. 將問題變成一連串的選擇
2. 找到一個「最佳選擇」的規則。

### 分析
:::warning
如果不能找到證明，那貪婪演算法通常會失效。
:::

技巧：
- 數學歸納法
- 矛盾證法
- 假設有更好的解法，證明「更好的解法」沒有比較好。

## Non-examples - 背包問題
### 0-1背包問題


**0-1 Knapsack:**
- 假設所有物品都是有限的。
- 怎麼填滿背包才能創造最大價值（Value）。

2個燈泡
- Total Weight: 4
- Total Value: 16

---

**"Greedy” algorithm for unbounded knapsack:**
Taco 有最佳的 value/weight（每單位重量的價值最高）。所以選 Taco
- Total Weight: 3
- Total Value: 13

### Unbounded Knapsack

---
> [name=李冠緯]

###### tags: `Algorithm`