# 窮舉和貪婪
## 4/23 資訊讀書會
---
# 窮舉和貪婪
----
窮舉和貪婪都是以最直覺的方法去解決題目，但是也有各自的缺點，需要去判斷適不適合用。
---
## 暴力搜尋法(窮舉)-概念
----
* 窮舉就是把所有可能的答案一個個試過，沒有漏掉的情況。
* 缺點是每一個都要試，會花太多時間。
* 不過因為很直覺，窮舉可以用來當作基礎，之後再改成其他的樣子。
* 加入條件、規律都可以減少執行次數。
* 像是深度優先和廣度優先都算是窮舉，不過比任意窮舉執行較少次數。
----
* 深度優先是先把一條跑到底，然後回到上一個分支的地方，再跑到底，一直到跑完。
* 廣度優先是每次都全部往前一步，直到沒有一個可以繼續走下去，類似水往外流。
---
## 窮舉-例題
----
## [ZeroJudeg-Print it all](https://zerojudge.tw/ShowProblem?problemid=a147)
輸出所有大於0、整數、不可以被7整除、小於n的數
(此題有多個輸入，若n=0則結束)
----
方法：把從1到n-1的整數列出來，再去掉七的倍數
### 程式碼
```cpp=
#include <bits/stdc++.h>
using namespace std;
int main(){
int n;
while(cin >> n){
if(!n) break;
for(int i=1; i<n; i++) if(i%7) cout << i << ' ';
cout << '\n';
}
return 0;
}
```
----
## [ZeroJudge-完全平方和](https://zerojudge.tw/ShowProblem?problemid=a059)
給定一個範圍a到b，找出a與b之間所有完全平方數的和。(測資有多筆輸入)
----
$舉出\sqrt{a}到\sqrt{b}之間的整數，並將其平方加總$
### 程式碼：
```cpp=
#include <bits/stdc++.h>
using namespace std;
int main(){
int n, a, b, c, d, s;
cin >> n;
for(int i=0; i<n; i++){
s=0;
cin >> a >> b;
c = ceil(sqrt(a));
d = floor(sqrt(b))+1;
for(int i=c; i<d; i++){
s+=i*i;
}
cout << "Case " << i+1 << ": " << s << '\n';
}
return 0;
}
```
---
## 回溯法
* 回溯法是在DFS到底之前，先提前得知這個方法不行，就可以先回去，減少浪費的時間。
----
## 經典例題：[八皇后問題](https://zerojudge.tw/ShowProblem?problemid=a160)
* 在一個n乘n的棋盤上，把n個皇后擺上，且彼此不能攻擊。(多筆輸入，到0結束)
* 這題要輸出整個棋盤，Q為皇后，x為空格
----
可以把行、列、兩個方向的斜線儲存皇后位置，皇后不能擺在已經有皇后的行、列、斜線。
程式碼：未完成
---
## 貪婪演算法-概念
----
* 貪婪演算法的想法是，如果每個決定都是當下最好的，那整體來說就會是最好的。
* 可是這不一定是對的，有時候會因為過早做決定而得到錯誤答案，這時候就要用動態規劃了。
---
## 貪婪演算法-例題
----
## [ZeroJudge-Product of digits](https://zerojudge.tw/ShowProblem?problemid=d418)
有l個大於0的整數N，找到最小的整數Q，使Q的每一位數乘起來是N。如果不存在這個Q，則輸出-1。
(測資有多筆輸入)
----
```cpp=
#include <bits/stdc++.h>
using namespace std;
int main(){
int l, n, q;
stack<int> st;
cin >> l;
while(l--){
cin >> n;
if(n==1){
cout << "1\n";
continue;
}
for(int i=9; i>1; i--){
while(n%i==0){
n/=i;
st.push(i);
}
if(n==1) break;
}
if(n!=1){
cout << "-1\n";
while(!st.empty()) st.pop();
continue;
}
while(!st.empty()){
cout << st.top();
st.pop();
}
cout << '\n';
}
return 0;
}
```
----
## 最大連續和-貪婪解法
這個題目雖然被歸類在動態規劃中，但其實也可以是貪婪的一種。
----
## [ZeroJudge-連續元素和](https://zerojudge.tw/ShowProblem?problemid=d784)
已知l個有n個元素的整數數列，找出每個數列連續元素和的最大值。
----
貪婪解法：
* 一邊累加一邊記得曾經出現過的最大累加值是多少
* 一旦累加的結果變成負值，就把累加歸零
* 同時也要記得最大的負數，如果發現沒有一個大於0，就輸出最大的那個負數
----
### 程式碼：
```cpp=
#include <bits/stdc++.h>
using namespace std;
int main(){
int l, n, m1, s, a, m2;
cin >> l;
while(l--){
m1=-1; s=0; m2=-10000;
cin >> n;
while(n--){
cin >> a;
if(a<0 && a>m2) m2=a;
s+=a;
if(s>m1) m1=s;
if(s<0) s=0;
}
if(m1>-1)cout << m1 << '\n';
else cout << m2 << '\n';
}
return 0;
}
```
---
## 不能用貪婪的例題
這種題目就是用貪婪法有些會錯的題目。
----
## DP問題-背包問題
* 在有限的最大重量下，盡可能把總價值最大的組合放進背包中。
* 這個題目的變種包含可否切割、東西的數量(單個、有限、無限)、放入的代價(時間、大小)。
* 湊硬幣也是背包問題的變種，不過重量就是價值。
----
## 貪婪的問題
只有可切割的才可以用貪婪解決，否則如果優先挑選價值最大的，有可能會剩下價值很低的縫隙，而這個縫隙跟其他東西合起來的重量，有可能可以換價值更高的。
{"title":"窮舉和貪婪","description":"窮舉和貪婪都是以最直覺的方法去解決題目，但是卻也有各自的缺點，需要去判斷適不適合用。","contributors":"[{\"id\":\"00ad9127-6491-4b3d-829b-7847a217f8e5\",\"add\":7534,\"del\":3961}]"}