贪心算法
贪心算法基本思路
image.png
贪心算法的基本思想
•贪心算法的特点是每个阶段所作的选择都是局部最优的，它期望通过所作的局部最优选择产生出一个全局最优解。
贪心与动态规划：与动态规划不同的是，贪心是鼠目寸光；动态规划是统揽全局。
–动态规划：每个阶段产生的都是全局最优解
•第i阶段的“全局”： 问题空间为(a1, … , ai)
•第i阶段的“全局最优解”：问题空间为 (a1, … , ai)时的最优解
–贪心：每个阶段产生的都是局部最优解
•第i阶段的“局部”：问题空间为按照贪心策略中的优先级排好序的第i个输入ai
•第i阶段的“局部最优解”： ai
贪心算法的基本要素
•贪心选择性质：所求问题的全局最优解可以通过一系列局部最优的选择（即贪心选择）来达到。
–这是贪心算法与动态规划算法的主要区别。
•最优子结构性质：当原问题的最优解包含子问题的最优解时，称此问题具有最优子结构性质。
最优子结构性质是该问题可用动态规划算法或贪心算法求解的关键特征
活动安排——贪心算法
•要求高效地安排一系列争用某一公共资源（例如会议室）的活动（使尽可能多的活动能兼容使用公共资源）。
–设有n个活动的集合E={e1,e2…en}，其中每个活动都要求使用同一资源，而在同一时间内只有一个活动能使用这一资源。每个活动i都有一个要求使用该资源的起始时间si和一个结束时间fi，且si<fi。如果选择了活动i，则它在半开时间区间[si,fi)内占用资源。
–若区间[si,fi)与区间[sj,fj)不相交，则称ei和ej是相容的。也就是说，当si≥fj或sj≥fi时，活动i和活动j相容。
•活动安排问题就是要在所给的活动集合中选出最大的相容活动子集合。
image.png
image.png
image.png
// 贪心算法-活动安排.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//
#include <iostream>
#include <algorithm>
using namespace std;
struct activity
{
int s;
int f;
int index;
};
bool cmp(activity a,activity b)
{
if (a.f <= b.f)
return true;
else
return false;
}
void GreedySelector(int n, activity a[], bool b[])
{
b[1] = true;
int pre = 1;
for (int i = 2;i <= n;i++)
{
if (a[i].s >= a[pre].f)
{
b[i] = 1;
pre = i;
}
}
}
int main()
{
int n;
cin >> n;
activity a[1000];
bool b[1000];
memset(b, false, sizeof(b));
for (int i = 1;i <= n;i++)
{
cin >> a[i].s >> a[i].f;
a[i].index = i;
}
sort(a, a + n + 1, cmp);
GreedySelector(n, a, b);
for (int i = 0;i <= n;i++)
{
if (b[i])
cout << a[i].index << " " << endl;
}
return 0;
}
