# Greedy(貪心演算法) ---- ## 演算法? ## 聽起來很難 ---- ## Q:什麼是greedy? ### A:每次都採取目前看起來最好的選擇 ---- # 教完了 uwu ---- # 範例 ## 找零問題 ---- #### 有面額 1、5、10、50的硬幣 #### 現在給你某個金額 #### 求最少需要多少硬幣才能組成上述的金額 #### ex: 56(3) ---- ## 不難發現最佳策略 #### 先用大的面額，直到剩下的金額比那個面額大 ---- ## 舉例: 498元 ## 先用50元 可取450元(剩48元) ## 再用10元 可取40元(剩8元) ## 再用5元 可取5元(剩3元) ## 最後用1元 取最後3元 ## 總共用了 9+4+1+3 = 17枚硬幣 ---- ```cpp= #include<iostream> using namespace std; int coin[4] = {50, 10, 5, 1}; int main(){ int n, ans; cin >> n; for(int i = 0; i < 4; i++){ ans += n/coin[i]; n %= coin[i]; } if(n==0) cout << ans << '\n'; else cout << "wtf\n"; } ``` ---- # 但是 ---- ## 如果增加一個面額為9元的硬幣 ## 還可以用greedy嗎? ---- ## 假設要換28元 ## greedy: 2\*10 + 1\*5 + 3*1 ## ans: 6枚 ---- ## 但其實最佳解是 ## 1\*10 + 2*9 ## 3枚 ---- # 所以 ## greedy不一定可以求出最佳解 #### greedy解不出來可以用dp解決(林士紘下次會教) ---- ## 練習題 ## CSDC #267 #### (因為我懶得出題，進階組的再寫一次吧) ---- ## ans ```cpp= #include<bits/stdc++.h> using namespace std; int main() { int p, total = 0; cin >> p; int arr[6] = {500, 100, 50, 10, 5, 1}; p = 1000*(p/1000+1)-p; for(int i = 0; i < 6; i++) { if(p>=arr[i]) { total += p/arr[i]; p%=arr[i]; } } cout << total << '\n'; }```