活動安排問題(貪心算法)
來源：程序員人生 發(fā)布時間：2014-12-13 08:31:16 閱讀次數(shù)：5602次
問題描寫：
有n個活動的活動集合E ，其中每個活動都要求使用同1個資源，而在同1個時刻內(nèi)資源只能被1個活動使用，每個活動都有開始是時間和結(jié)束時間，要求從活動集合E當(dāng)選出m個活動，使著m個活動都能順利進(jìn)行，即也就是每一個活動的活動時間都相互不交叉，求m的最大值和 被選中的活動序號。
例如輸入：
活動編號 活動開始時間 活動結(jié)束時間
1 1 4
2 3 5
3 0 6
4 5 7
5 3 8
6 5 9
7 6 10
8 8 11
9 8 12
10 2 13
11 12 14
本程序利用貪心算法解決，輸出的答案是：
應(yīng)當(dāng)選擇的活動編號為：
1 4 8 11（即最大可以安排這4個活動）
#include<iostream>
#include<iterator>
#include<vector>
#include<algorithm>
using namespace std;
/*
*活動安排問題(貪心算法)
*/
struct Act
{
int beg;//活動的開始時間
int end;//活動的結(jié)束時間
int index;//活動的編號
friend ostream & operator<<(ostream &o,const Act &A);
friend istream & operator>>(istream &o, Act &A);
};
ostream & operator<<(ostream &o,const Act &A)
{
o<<A.beg<<"---"<<A.end<<" ";
return o;
}
istream & operator>>(istream &o, Act &A)
{
o>>A.index>>A.beg>>A.end;
return o;
}
bool cmp(Act & act1,Act & act2)
{
if(act1.end<act2.end)
{
return true;
}else
{
return false;
}
}
vector<int> GreedySelector(vector<Act> & acts)
{
//首先把活動依照活動的結(jié)束時間進(jìn)行排序
sort(acts.begin(),acts.end(),cmp);
//在排序后的活動集合當(dāng)選擇可行的活動
vector<int> res;
res.push_back(acts[0].index);//首先選中第1個活動
int now = 0;//當(dāng)前選中的活動下標(biāo)
for (int i = 1; i < acts.size(); i++)
{
if(acts[i].beg>=acts[now].end)
{
now = i;
res.push_back(acts[i].index);
}
}
return res;
}
int main()
{
vector<Act> acts;//可選活動集
copy(istream_iterator<Act>(cin),istream_iterator<Act>(),back_inserter(acts));
cout<<endl;
vector<int> res_act;//得出的方案中的活動編號集
res_act = GreedySelector(acts);
//輸出結(jié)果
copy(res_act.begin(),res_act.end(),ostream_iterator<int>(cout," "));
cout<<endl;
}
生活不易，碼農(nóng)辛苦
如果您覺得本網(wǎng)站對您的學(xué)習(xí)有所幫助,可以手機掃描二維碼進(jìn)行捐贈
