貪心演算法
一、貪心演算法
貪心演算法不是對所有問題都能得到整體最優解，關鍵是貪心策略的選擇。也就是說，不從整體最優上加以考慮，做出的只是在某種意義上的局部最優解
二、例題
例題一、區間問題
問題描述：
有n項工作，每項工作分別在si開始，ti結束。對每項工作，你都可以選擇參加或不參加，但選擇了參加某項工作就必須至始至終參加全程參與，即參與工作的時間段不能有重疊(即使開始的時間和結束的時間重疊都不行)。
限制條件：
1<=n<=100000
1<=si<=ti,=109
樣例：
輸入
5
1 2 4 6 8
3 5 7 9 10
輸出
3(選擇工作1, 3, 5)
題解：有三種演算法：一是挑選開始時間最早的方案，二是挑選重疊次數最少的方案，三是結束時間最早的方案。經選擇，選擇方案三
程式碼：
#include<iostream>
#include<algorithm>
#include<string>
#include<utility>
#define maxn 100005
using namespace std;
typedef pair<int,int> P;
int N,endtime[maxn],starttime[maxn];
P pai[maxn];
int tanxin()
{
for(int i=0;i<N;i++)
{
pai[i].first=endtime[i];
pai[i].second=starttime[i];
}
sort(pai,pai+N);//默認先對first排序，再對second排序
int t=pai[0].first;
int ans=1;
for(int i=0;i<N;i++)
{
if(t<pai[i].second)
{
t=pai[i].first;
ans++;
}
}
return ans;
}
int main()
{
while(cin>>N)
{
for(int i=0;i<N;i++)
cin>>starttime[i];
for(int i=0;i<N;i++)
cin>>endtime[i];
int ans=tanxin();
cout<<ans<<endl;
}
return 0;
}
例題二、分餅乾
假設你是一位很棒的家長，想要給你的孩子們一些小餅乾。但是，每個孩子最多只能給一塊餅乾。對每個孩子 i ，都有一個胃口值 gi ，這是能讓孩子們滿足胃口的餅乾的最小尺寸；並且每塊餅乾 j ，都有一個尺寸 sj 。如果 sj >= gi ，我們可以將這個餅乾 j 分配給孩子 i ，這個孩子會得到滿足。你的目標是儘可能滿足越多數量的孩子，並輸出這個最大數值
樣例
輸入:3 2
1 2 3
1 1
輸出: 1
題解：本題採用貪心策略。將餅乾和孩子需要的從小到大排序，然後選擇按順序選擇餅乾。
程式碼
#include<iostream>
#include<string>
#include<algorithm>
#define maxn 100005
using namespace std;
int main()
{
int N,M,cookie[maxn],stu[maxn];
while(cin>>N>>M&&M)
{
int ans=0;
for(int i=0;i<N;i++)
cin>>cookie[i];
for(int i=0;i<M;i++)
cin>>stu[i];
sort(cookie,cookie+N);
sort(stu,stu+M);
for(int c=0,s=0;s<M&&c<N;c++)
{
if(stu[s]>=cookie[c])
{
ans++;
s++;
}
if(stu[s]<cookie[c])
continue;
}
cout<<ans<<endl;
}
return 0;
}
