# Week 13~14：貪心法 Greedy
要點：貪心，要更多、更快、更好的結果
對於任何情況，都選當下最好的選擇，如此便能得到問題的最佳解
並非所有問題都能用greedy
能用greedy 的題目通常具有以下性質：
1. 最佳解會包含子問題的最佳解
2. 最佳解通常可以由當下最好的選擇得到
通常會先定義「貪心法則」，如何選擇才是目前的最佳解，解決小問題
接下來不斷重複用「貪心法則」，找到每個小問題的最佳解，直到解決整個問題
## Fractional Knapsack Problem
問題：有個背包可以裝M克的物品，現在有n種礦石，每種礦石都有各自的價錢$p_i$和存量$w_i$，每裝進$x_i$克的礦石能得到$p_i$ x $x_i$ 元(須滿足$x_i$≤$w_i$,$\sum_{i=1}^nx_i$≤M)，問最多能賺到多少錢?
想法：每種礦石不一定要拿完，可以只拿一部份→簡化為拿M克礦石能賺錢的最大值→從價值最高的開始greedy，直到背包沒有空間
```cpp=
#include <bits/stdc++.h>
using namespace std;
struct rock
{
int price;
int weight;
}a[1005];
bool cmp(rock a,rock b)
{
return a.price>b.price;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
int n,m;
cin>>n>>m;
for(int i=0;i<n;i++) cin>>a[i].weight>>a[i].price;
sort(a,a+n,cmp);
int ans=0;
for(int i=0;i<n;i++)
{
if(m>=a[i].weight)
{
ans+=a[i].weight*a[i].price;
w-=a[i].weight;
}
else
{
ans+=a[i].price*m;
break;
}
}
cout<<ans<<endl;
return 0;
}
```
## 誰先晚餐
問題：有n個人每個人恰點了一份餐，餐點要花$c_i$分製作，$t_i$分食用，請問該如何安排製作餐點的順序才能使所有人都吃完的時間最短?
想法：先從做食用時間長的人的餐點開始greedy，可以在食用時間比較短的人等餐食開始吃，廚師做餐的時間是固定的$\sum_{i=1}^nc_i$。
```cpp=
#include <bits/stdc++.h>
using namespace std;
struct people
{
int t,c;
}a[1005];
bool cmp(people a,people b)
{
return a.t>b.t;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
int n,m;
cin>>n>>m;
for(int i=0;i<n;i++)
{
cin>>a[i].c>>a[i].t;
}
sort(a,a+n,cmp);
int now=0, ans=0;
for(int i=0;i<n;i++)
{
now+=a[i].c;
ans=max(ans,now+a[i].t);
}
cout<<ans<<endl;
return 0;
}
```
## Movie Festival
問題：有n場電影要放映，給每場電影的開始與結束時間，問最多可以看幾場電影?(同時間只能看一場電影，且一定要完整看完)
想法：越早看完就葛以越早開始看下一場電影。
```cpp=
#include <bits/stdc++.h>
#define ll long long
using namespace std;
struct movie
{
ll l;
ll r;
}a[2000005];
bool cmp(movie a,movie b)
{
if(a.r!=b.r) return a.r<b.r;
return a.l<b.l;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
int n;
cin>>n;
for(int i=0;i<n;i++) cin>>a[i].l>>a[i].r;
sort(a,a+n,cmp);
ll ans=0,now=-1;
for(int i=0;i<n;i++)
{
if(a[i].l>=now)
{
ans++;
now=a[i].r;
}
}
cout<<ans<<endl;
return 0;
}
```
## Many task problem
問題：有n個人下了訂單，每筆有各自的完成所需時間$t_i$，問要如何安排訂單順序才能使等待時間總和最短?
想法：所需時間越短的時間要先做→放在越前面，後面等的人就越多。
假設t[i]是第i筆訂單所需時間，答案會是$\sum_{i=1}^n(n-i+1)$ x $t[i]$→讓越小的乘比較多次→放越前面做
```cpp=
#include <bits/stdc++.h>
using namespace std;
bool cmp(int a,int b)
{
return a<b;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
int n;
while(cin>>n)
{
for(int i=0;i<n;i++)
{
cin>>a[i];
}
sort(a,a+n,cmp);
int now=0,ans=0;
for(int i=0;i<n-1;i++)
{
now+=a[i];
ans+=now;
}
cout<<ans<<endl;
}
return 0;
}
```
## Tasks and Deadlines
問題：有n個任務要完成，每個任務都有各自的完成期限$deadline_i$和利潤$profit_i$，問要如何排序才能使每個任務都在期限內完成且利潤最大?
想法：依照利潤由大到小排序，接著遍歷每個任務並確保在期限內完成
```cpp=
#include <bits/stdc++.h>
using namespace std;
struct task
{
int job_id;
int deadline;
int profit;
}a[100005];
bool cmp(task a,task b)
{
return a.profit>b.profit;
}
void tasksequence(task a[],int num)
{
sort(a,a+n,cmp);
int result[num];
bool s[num];
memset(s,0,sizeof(s));
for(int i=0;i<num;i++)
{
for(int j=min(num,a[i].deadline)-1;j>=0;j--)
{
if(s[j]==false)
{
result[j]==i;
s[j]=true;
break;
}
}
}
for(int i=0;i<num;i++)
{
if(s[i]==true)
{
cout<<a[result[i]].job_id<<" ";
}
}
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
int n;
cin>n;
for(int i=0;i<n;i++) cin>>a[i].job_id>>a[i].deadline>>a[i].profit;
tasksequence(a,num);
}
```
## Many tasks with weight
問題：有n個客人下了一筆訂單，每筆有各自的完成時間$t_i$、重要性$w_i$，價錢$v_i$，訂單的計價方式為：設第i個任務在f分時完成，可以賺到$v_i-f$ x $w_i$，問要如何安排訂單順序以賺最多錢?
想法：$\sum_{i=1}^nv_i$為定值，需要考慮$w_i$，因此$t_i$短或$w_i$大排在前面不一定比較好→讓w/t值越大的排在越前面
證明：根據假設，w/t值越大的會排在越前面，可以找到任兩個訂單w[i]/t[i]>w[i+1]/t[i+1]，若交換兩者順序，其他訂單不會受影響，則w[i]延後了t[i+1]，w[i+1]提早了t[i]，賺到的錢變化為w[i] x t[i+1] - w[i+1] x t[i] >0，賺到的錢變多
```cpp=
#include <bits/stdc++.h>
#define ll long long
using namespace std;
struct task
{
ll t;
ll w;
ll v;
}a[1005];
bool cmp(task a,task b)
{
return 1.0*a.w/a.t>1.0*b.w/b.t;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
ll n;
cin>>n;
for(int i=0;i<n;i++) cin>>a[i].t>>a[i].w>>a[i].v;
sort(a,a+n,cmp);
ll now=0,ans=0;
for(int i=0;i<n;i++)
{
now+=a[i].t;
ans+=a[i].v-now*a[i].w;
}
cout<<ans<<endl;
return 0;
}
```
Sign in with Wallet
Connect another wallet