# Greedy Algorithms
By Colin
---
## Greedy Algorithms 貪婪演算法
- 每個步驟都選擇當下最佳的選擇
- 透過一次次局部最佳解獲得全局最佳解
- 通常具有較低的時間複雜度
- 不是所有問題都可以用Greedy解決
---
- 來看些例子吧
---
Example 1: 付錢問題
[CSDC267 請支援收銀](https://csdc.tw/problem/267/)
[CSDC348 出國囉!](https://csdc.tw/problem/348/)
假設有1000元、500元、100元、50元、10元、5元、1元共七種面額的紙鈔各無限多張，若要付$n$元，則最少需要以幾張紙鈔支付(不可找零)？
----
想法：
- 只要一直以最大面額的鈔票支付，必定可以以最少張數湊出$n$元
- 例如：
- 12789元=
- 1000元\*12張 + 500元\*1張 + 100元\*2張 + 50元\*1張 + 10元\*3張 + 5元\*1張 + 1元\*4張
- 共24張鈔票
----
CSDC267 請支援收銀 AC code
```cpp=
#include <iostream>
#define int long long
#define horaceorz ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
using namespace std;
int arr[7]={1000,500,100,50,10,5,1};
signed main(){
int n,ans=0; cin>>n;
int a=n/1000;
n=(a+1)*1000-n;
for(int i=0;i<7;i++){
ans+=n/arr[i];
n%=arr[i];
}
cout<<ans;
return 0;
}
```
----
CSDC348 出國囉! AC code
```cpp=
#include <bits/stdc++.h>
#define int long long
#define horaceorz ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
using namespace std;
signed main(){
int N,a=0,b=0; cin>>N;
N*=4;
int value[10]={10000,5000,2000,1000,500,100,50,10,5,1};
for(int i=0;i<10;i++){
if(N>=value[i]){
if(i<=3) a+=N/value[i];
else b+=N/value[i];
N%=value[i];
}
}
cout<<a<<' '<<b<<'\n';
return 0;
}
```
----
- 付錢問題可以Greedy的條件是每種紙鈔的面額呈整數倍關係
- 若不是，則可能會有問題
- 例如：有1000元、900元、100元共三種面額的紙鈔，若要付1800元，若照前述作法需要1000元\*1張 + 100元\*8張 共9張鈔票，但最佳解為900元\*2張 共2張鈔票。遇到這種情形就要用DP解決(找零錢問題)
----
找零錢問題[Minimizing Coins](https://cses.fi/problemset/task/1634)
DP解(無限背包問題)
```cpp=
//陣列太大會RE
//dp(bottom up)
//時間複雜度:O(nx)
//空間複雜度:O(nx)
#include <bits/stdc++.h>
#define int long long
#define horaceorz ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
using namespace std;
int n,x;
vector<int> c(105);
vector<vector<int>> dp(105,vector<int>(1000005,1e18));
signed main(){
//horaceorz;
cin>>n>>x;
for(int i=1;i<=n;i++) cin>>c[i];
for(int i=0;i<=n;i++) dp[i][0]=0;
for(int i=1;i<=n;i++){
for(int j=1;j<=x;j++){
if(j>=c[i]) dp[i][j]=min(dp[i-1][j],dp[i][j-c[i]]+1);
else dp[i][j]=dp[i-1][j];
}
}
if(dp[n][x]>x) cout<<-1<<'\n';
else cout<<dp[n][x]<<'\n';
return 0;
}
```
----
AC code
```cpp=
//dp(bottom up)+滾動數組優化
//時間複雜度:O(nx)
//空間複雜度:O(x)
#include <bits/stdc++.h>
#define int long long
#define horaceorz ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
using namespace std;
int n,x;
vector<int> c(105);
vector<int> dp(1000005,1e18);
signed main(){
//horaceorz;
cin>>n>>x;
for(int i=1;i<=n;i++) cin>>c[i];
dp[0]=0;
for(int i=1;i<=n;i++){
for(int j=c[i];j<=x;j++){
dp[j]=min(dp[j],dp[j-c[i]]+1);
}
}
if(dp[x]>x) cout<<-1<<'\n';
else cout<<dp[x]<<'\n';
return 0;
}
```
---
Example 2: 最佳對戰組合問題
[zerojudge n175. 田忌賽馬](https://zerojudge.tw/ShowProblem?problemid=n175)
對戰雙方各有$n$名選手，要比$n$場比賽，每位選手都必須出戰一場。已知雙方每位選手的戰力值，以及對方出賽的順序，比賽時雙方派出的選手戰力值較高者勝，求我方最多能贏幾場比賽？
----
- 遇到類似Greedy問題就要大膽的猜～
----
想法：
- 每次都以我方目前最弱的選手去對戰對方目前最弱的選手，一定可以得到最佳解
----
證明：
- 假設我方目前最弱的戰力是$a$，對方目前最弱的戰力是$b$
- Case1: $a\le b$
- $a$必輸或平手，可以忽略
----
- Case2: $a>b$
- 我方:$a,y$，對方:$b,x$
- 若最佳解中，$a$對戰$x$(輸贏不一定)而$y$對戰$b$(必贏)，將其交換改成$a$對$b$(必贏)而$y$對$x$(輸贏不一定)
- 根據假設可知$b<a\le y$且$b\le x$
- 若$b<a\le y\le x$，交換前後戰績皆不變
- 若$b<a\le x\le y$，交換後戰績可能增加或不變
- 若$b\le x<a\le y$，交換前後戰績皆不變
- 綜上所述，交換後的戰績不會比交換前差
- 所以「每次都以我方目前最弱的選手去對戰對方目前最弱的選手，一定可以得到最佳解」成立
----
zerojudge n175. 田忌賽馬 AC code
```cpp=
#include <bits/stdc++.h>
#define int long long
#define horaceorz ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
using namespace std;
int n,general[200005],king[200005],ans=0;
signed main(){
horaceorz;
cin>>n;
for(int i=0;i<n;i++) cin>>general[i];
for(int i=0;i<n;i++) cin>>king[i];
sort(general,general+n);
sort(king,king+n);
for(int i=n-1,j=n-1;i>=0&&j>=0;i--){
if(general[i]<king[j]){
ans++; j--;
}
}
cout<<ans<<'\n';
return 0;
}
```
---
Example 3: 最小完成時間總和
[zerojudge n174. 非常不妙的寒假作業](https://zerojudge.tw/ShowProblem?problemid=n174)
有$n$項工作，已知完成每項工作所需花費時間，求每項工作完成的最小時間總和為何？
----
例如有5項工作，完成每項工作所需花費時間分別為3,2,5,1,4
若按照這個順序，
- 第一項作業完成的時間=3
- 第二項作業完成的時間=3+2=5
- 第三項作業完成的時間=3+2+5=10
- 第四項作業完成的時間=3+2+5+1=11
- 第五項作業完成的時間=3+2+5+1+4=15
- 每項作業完成的時間總和=3+5+10+11+15=44
----
想法：
- 從花費時間最少的工作開始做，必可得到每項工作完成的最小時間總和
----
證明：
- 假設最佳的工作順序是從第$1$項~第$n$項
- 若存在兩項工作符合$cost[i]>cost[i+1]$
- 若交換這兩項工作，第$1$~$i-1$項與第 $i+1$~$n$項工作完成的時間總和皆不會改變，但第$i$項完成的時間總和會變小
- 所以「從花費時間最少的工作開始做，必可得到每項工作完成的最小時間總和」成立
----
zerojudge n174. 非常不妙的寒假作業 AC code
```cpp=
#include <bits/stdc++.h>
#define int long long
#define horaceorz ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
using namespace std;
int n,arr[200005],ans=0;
signed main(){
horaceorz;
cin>>n;
for(int i=0;i<n;i++){
string s; cin>>s>>arr[i];
}
sort(arr,arr+n);
for(int i=0,p=0;i<n;i++){
p+=arr[i]; ans+=p;
}
cout<<ans<<'\n';
return 0;
}
```
---
Example 4: 線段覆蓋長度
[2016.03 APCS 3. 線段覆蓋長度](https://zerojudge.tw/ShowProblem?problemid=b966)
在一維座標軸上有$n$段線段，已知每段線段的兩端點座標，求此$n$段線段覆蓋的總長度為何？
----
想法：
- 將所有線段依左端點座標排序
- 遍歷所有線段，設原線段左端點為$L$，右端點為$R$
- 若新線段$l>R$，則令$ans+=R-L，L=l，R=r$
- 若新線段$l\le R$且$r>R$，則令$R=r$
- 若新線段$l\le R$且$r\le R$，則不須更動$L,R$
----
AC code
```cpp=
#include <bits/stdc++.h>
#define int long long
#define horaceorz ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define l first
#define r second
using namespace std;
int n,ans=0;
vector<pair<int,int>> seg(10005);
signed main(){
//horaceorz;
cin>>n;
for(int i=0;i<n;i++) cin>>seg[i].l>>seg[i].r;
sort(seg.begin(),seg.begin()+n);
int L=seg[0].l,R=seg[0].r;
for(int i=1;i<n;i++){
if(seg[i].l>R){
ans+=R-L;
L=seg[i].l;
R=seg[i].r;
}else if(seg[i].r>R){
R=seg[i].r;
}
}
ans+=R-L;
cout<<ans<<'\n';
return 0;
}
```
---
Example 5: 交換的Greedy
[CSDC238 不會整理書的笨蛋](https://csdc.tw/problem/238/)
[2017.10 APCS 4. 物品堆疊](https://zerojudge.tw/ShowProblem?problemid=c471)
----
想法：
- 重量(W)、次數(T)皆會影響最佳放置順序
- 重量(W)越輕要放越上面
- 次數(T)越多要放越上面
- =>$\frac{重量(W)}{次數(T)}越小要放越上面$
- 假設第$i$本書放在第$i+1$本書上面
- =>$\frac{W_i}{T_i}<\frac{W_{i+1}}{T_{i+1}}$
- =>$W_i\times T_{i+1}<W_{i+1}\times T_i$
----
AC code
```cpp=
#include <bits/stdc++.h>
#define int long long
#define horaceorz ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
using namespace std;
struct book{
int w,t;
};
bool cmp(book a,book b){
return a.w*b.t<b.w*a.t;
}
int n,ans=0;
vector<book> arr(100005);
signed main(){
//horaceorz;
cin>>n;
for(int i=0;i<n;i++) cin>>arr[i].w;
for(int i=0;i<n;i++) cin>>arr[i].t;
sort(arr.begin(),arr.begin()+n,cmp);
int W=arr[0].w;
for(int i=1;i<n;i++){
ans+=W*arr[i].t;
W+=arr[i].w;
}
cout<<ans<<'\n';
return 0;
}
```
---
Example 6: 排程問題
[2023.01 APCS 4. 機器出租](https://zerojudge.tw/ShowProblem?problemid=j608)
----
想法：
- 將所有活動依照結束時間排序
- 設$free[i]$表示第$i$個機器上一個舉辦的活動的結束時間
- 如果$k$個機器中$free$最小的$\ge$當前活動的開始時間，則此活動不可能被舉辦，不必繼續檢查
- 否則找到可以舉辦當前活動的機器中free最大的=>浪費的時間最少
----
AC code
```cpp=
#include <bits/stdc++.h>
#define int long long
#define horaceorz ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
using namespace std;
struct job{
int l,r;
};
bool cmp(job a,job b){
return a.r<b.r;
}
int n,k,ans=0;
vector<job> arr(100005);
vector<int> Free(105,0);
signed main(){
//horaceorz;
cin>>n>>k;
for(int i=0;i<n;i++) cin>>arr[i].l;
for(int i=0;i<n;i++) cin>>arr[i].r;
sort(arr.begin(),arr.begin()+n,cmp);
for(int i=0;i<n;i++){
int mini=1e18,idx_mini;
for(int j=0;j<k;j++){
if(Free[j]<mini){
mini=Free[j]; idx_mini=j;
}
}
if(mini>=arr[i].l) continue;
int maxi=-1e18,idx_maxi;
for(int j=0;j<k;j++){
if(Free[j]<arr[i].l){
if(Free[j]>maxi){
maxi=Free[j]; idx_maxi=j;
}
}
}
Free[idx_maxi]=arr[i].r;
ans++;
}
cout<<ans<<'\n';
return 0;
}
```
---
練習題：
[CSDC205 泡泡與她的小石頭](https://csdc.tw/problem/205/)
[CSDC192 種菜好好玩](https://csdc.tw/problem/192/)
[CSDC316 當你發現你的Greedy不夠Greedy](https://csdc.tw/problem/316/)
[112北二 3a.忍術學園的期中考](https://zerojudge.tw/ShowProblem?problemid=m603)
---
Thank you for listening!
{"description":"By Colin","title":"Greedy Algorithms","contributors":"[{\"id\":\"fd160699-cd06-45fd-abd0-c09edbc85980\",\"add\":9248,\"del\":709}]"}