# 貪婪法 --- ## 什麼是貪婪法 貪婪法是以最直覺的方式去解決問題。 貪婪法認為如果每個決定都是當下最好的，那總體的結果就會是最好的。 ---- ## 可以用貪婪法的時候 1. 有辦法判斷當前最佳解 2. 選擇全體最佳解，代表選出了當前最佳解 --- ### 例題1 個位數相乘[ZJ d418.](https://zerojudge.tw/ShowProblem?problemid=d418) 給定一個正整數$N$，找到最小的正整數$Q$， 使得$Q$的每一位的相乘為$N$。 若不能，則輸出-1。 ---- ### 解題想法 * 因為要找最小的整數，所以我們應該要讓它的位數盡可能少，也就是從最大的開始除。 * 所以先不斷的除9，接著除8，一路到2。 * 最後把最小的先輸出，大的排在後面。 ---- ### 程式範例 ```cpp= #include <bits/stdc++.h> using namespace std; int main(){ int l, n, q; stack<int> st; cin >> l; while(l--){ // 重複l次 cin >> n; for(int i=9; n!=1 && i>1; i--){ // 從大的開始除 while(n%i==0){ n/=i; st.push(i); } } if(n!=1){ // 如果沒除完，代表沒辦法拆成整數相乘 cout << "-1\n"; while(!st.empty()) st.pop(); // 清空 continue; } while(!st.empty()){ // 輸出並清空 cout << st.top(); st.pop(); } cout << '\n'; // 換行 } return 0; } ``` --- ### 例題2 最大連續和[ZJ d784.](https://zerojudge.tw/ShowProblem?problemid=d784) 給一段長度$n$的數列$\{a\}$ 找出一個連續子數列，使該數列的和最大。 該子數列不能為空 ---- ### 解題想法 * 如果有一個連續子數列的和是正的，那 它加上後面的就可能變得更大。 * 但如果這個子數列和是負的，那就不要把它和 後面的加起來，才不會讓後面的變小。 ---- ### 程式範例 ```cpp= #include <bits/stdc++.h> using namespace std; int main(){ int l, n, s, a, m1, m2; // s：當前子數列和，m1：最大值，m2：最大的負數 cin >> l; while(l--){ // 重複l次 m1=-1; s=0; m2=-10000; // 設為最小值 cin >> n; while(n--){ // 重複n次 cin >> a; if(a<0 && a>m2) m2=a; // 存最大的負數，以免全是負的 s+=a; if(s>m1) m1=s; // 更新最大值 if(s<0) s=0; // 如果和比0小，就不要留下 } if(m1>-1)cout << m1 << '\n'; // 如果有不是負的 else cout << m2 << '\n'; } return 0; } ``` --- # 不能用貪婪法的時候 ---- ## 貪婪法的缺點 有的時候，先選當下最好的，反而會 沒辦法找到整體最好的。 ---- ### 背包問題 背包問題是常見的形式是在有限的背包容量下，裝下總價值最高的物品。 有時候會改成要總價值最低的。 ---- ### 旅行推銷員問題 有一系列城市，與在他們彼此之間的距離。 求可以經過每個城市恰一次後，回到原處的最短迴路。