---
# System prepended metadata

title: Week 13~14：貪心法 Greedy
tags: ['#自主學習']

---

# 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;
}
```