---
tags: blind75, it 鐵人賽
---
# 圖解 blind 75: Greedy 策略簡介

## Greedy 策略簡介

[Greedy 策略](https://en.wikipedia.org/wiki/Greedy_algorithm) 是種解決問題的策略。

類似於[動態規劃](https://en.wikipedia.org/wiki/Dynamic_programming) ，[Greedy 策略](https://en.wikipedia.org/wiki/Greedy_algorithm) 也是透過把原本問題拆解成子問題去解。每次解決子問題都選擇最佳解的解決方案，從而導出整體的最佳解。

[Greedy 策略](https://en.wikipedia.org/wiki/Greedy_algorithm)特別適合有最佳子結構且子問題不重複的問題。

所謂最佳子結構的意思是局部最佳解能決定全域最佳解。

簡單地說，問題能夠分解成子問題來解決，子問題的最佳解能遞推到最終問題的最佳解。

[Greedy 策略](https://en.wikipedia.org/wiki/Greedy_algorithm)的最大特性就是每個子問題都選取最佳解來往下推導全局最佳解。

另一個不同於[動態規劃](https://en.wikipedia.org/wiki/Dynamic_programming)，[Greedy 策略](https://en.wikipedia.org/wiki/Greedy_algorithm)對於每個子問題解決方案都必須做選擇，且選擇了不能往上個結果去尋找，也就是只有一個最佳解。

局部的最佳解可以決定全局的最佳解。

[Greedy 策略](https://en.wikipedia.org/wiki/Greedy_algorithm)可以用來解決一些最佳化的問題，比如圖論中的[最小生成樹](https://zh.wikipedia.org/zh-tw/%E6%9C%80%E5%B0%8F%E7%94%9F%E6%88%90%E6%A0%91)問題，[霍夫曼編碼](https://zh.wikipedia.org/zh-tw/%E9%9C%8D%E5%A4%AB%E6%9B%BC%E7%BC%96%E7%A0%81) 等等。

而其他問題，使用[Greedy 策略](https://en.wikipedia.org/wiki/Greedy_algorithm)不一定找的出解法。

[Greedy 策略](https://en.wikipedia.org/wiki/Greedy_algorithm)可以說是 [動態規劃](https://en.wikipedia.org/wiki/Dynamic_programming)的一種特例。

### 換硬幣問題 - 說明使用 Greedy 策略的時機

#### 換最少硬幣個數問題(在每個幣值之間如果都具有倍數關係的情況下)

舉例來說： 幣值有 1, 5, 10, 50 ，其中 50 是 10, 5, 1的倍數，且 10 是 5, 1 的倍數， 5 是倍數。

在這時適合用 [Greedy 策略](https://en.wikipedia.org/wiki/Greedy_algorithm)，

因為這個問題具有以下特性：

1. 具有最佳子問題結構
2. 局部最佳解可以組成全局最佳解
3. 子問題彼此不重疊

也就是：幣值最大使用愈多換得的硬幣愈少

使用 [Greedy 策略](https://en.wikipedia.org/wiki/Greedy_algorithm) 就是幣值愈大愈先兌換

假設要換 120 -> 50 * 2 + 10 * 2 => 一共 4 枚硬幣

#### 換最少硬幣個數問題(在每個幣值之間不一定倍數關係的情況下)

然而，一般來說大部分的問題，局部最佳解未必是全域最佳解。

所以子問題的最佳解未必能能組成整個問題的最佳解

換最少硬幣問題中，假設幣值並非都有倍數關係

舉例來說： 幣值 1, 3, 4, 5 要兌換 7

如果使用 [Greedy 策略](https://en.wikipedia.org/wiki/Greedy_algorithm) 就是幣值愈大愈先兌換

會得到 7 -> 5 * 1 + 1* 2 => 一共 3 枚硬幣

然而卻有更少的換法 7 -> 3 * 1 + 4 * 1 => 一共 2枚硬幣 的換法

其原因是當幣值之間不一定是倍數關係時，此問題局部最佳解不一定組成全局最佳解

使用幣值最大使用愈多換得的硬幣不一定愈少

### 小故事

某個公司會議中

老闆：這次的新產品主題希望是夠創新且有發展性的東西，不知道大家有什麼想法？

主管a: 現在 ai 似互很流行，舉例： ai 在量化交易

主管b: Web3 也不錯，一堆公司要做 Dapp 應用。

同事c: 聽說 ar 很多硬體大廠都支援了，元宇宙正夯。

同事d: iot 然後蒐集大數據，然後做資料分析，好像也很流行！

老闆： 那不如把這些主體都結合在一起，大家覺得如何？

ar 內容然後加入 iot 把資料寫入 blockchain 用 智能合約跑數據分析

所有創新且有發展性都主題都放在一起了

同事e: 是沒聽過這麼酷的產品！

但我知道國產零零七的達文西為了對付金槍客

把七種獨當一面的武器集合起來合成"要你命3000"


### 後話

有時候局部最佳解不一定是全局最佳解。