贪心算法

定义：

贪心算法（greedy algorithm ，又称贪婪算法）是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，算法得到的是在某种意义上的局部最优解 。

贪心算法不是对所有问题都能得到整体最优解，关键是贪心策略的选择。

算法思路：

贪心算法一般按如下步骤进行：

①建立数学模型来描述问题 。

②把求解的问题分成若干个子问题 。

③对每个子问题求解，得到子问题的局部最优解 。

④把子问题的解局部最优解合成原来解问题的一个解 。

贪心算法是一种对某些求最优解问题的更简单、更迅速的设计技术。贪心算法的特点是一步一步地进行，常以当前情况为基础根据某个优化测度作最优选择，而不考虑各种可能的整体情况，省去了为找最优解要穷尽所有可能而必须耗费的大量时间。

贪心算法采用自顶向下，以迭代的方法做出相继的贪心选择，每做一次贪心选择，就将所求问题简化为一个规模更小的子问题，通过每一步贪心选择，可得到问题的一个最优解。虽然每一步上都要保证能获得局部最优解，但由此产生的全局解有时不一定是最优的，所以贪心算法不要回溯。

算法特性：

贪心算法可解决的问题通常大部分都有如下的特性：

1、有一个以最优方式来解决的问题。为了构造问题的解决方案，有一个候选的对象的集合：比如不同面值的硬币 。

2、随着算法的进行，将积累起其他两个集合：一个包含已经被考虑过并被选出的候选对象，另一个包含已经被考虑过但被丢弃的候选对象。

3、有一个函数来检查一个候选对象的集合是否提供了问题的解答。该函数不考虑此时的解决方法是否最优。

4、还有一个函数检查是否一个候选对象的集合是可行的，即是否可能往该集合上添加更多的候选对象以获得一个解。和上一个函数一样，此时不考虑解决方法的最优性。

5、选择函数可以指出哪一个剩余的候选对象最有希望构成问题的解。

6、最后，目标函数给出解的值 。

使用条件

利用贪心法求解的问题应具备如下2个特征 。

1、贪心选择性质

一个问题的整体最优解可通过一系列局部的最优解的选择达到，并且每次的选择可以依赖以前作出的选择，但不依赖于后面要作出的选择。这就是贪心选择性质。对于一个具体问题，要确定它是否具有贪心选择性质，必须证明每一步所作的贪心选择最终导致问题的整体最优解。

2、最优的结构性质

当一个问题的最优解包含其子问题的最优解时，称此问题具有最优子结构性质。问题的最优的结构性质是该问题可用贪心法求解的关键所在。在实际应用中，至于什么问题具有什么样的贪心选择性质是不确定的，需要具体问题具体分析。

例题分析：

超市里有n个产品要卖，每个产品都有一个截至时间dx（从开始卖时算起），只有在这个截至时间之前才能卖出并且获得利润dy。

有多个产品，产品可以有不同的卖出顺序，每卖一个产品要占用1个单位的时间，问最多能卖出多少利润。

输入一

4

50 2

10 1

20 2

30 1

输出一

80

输入二

7

20 1

2 1

10 3

100 2

8 2

5 20

50 10

输出二

185

思路：

先把所有产品按照利润从大到小排序，然后这个把这个放在截止日期那天卖出，并做好标记，如果截止日期那天已经有其他产品占用了，那么可以把这个产品卖出的时间往前推，直到找到可以卖的那一天并标记好。

假设一个产品a占用了一个日期后，那么如果下次又有一个产品b和产品a的截止日期是相同的，但是那个日期已被占用了，所以就要往前移动1天，那么就可以用并查集进行标记，在a占用了那个日期后，把a的截止日期指向前一个日期，这样的话，可以直接查找到他要占用到哪一个时间。

代码实现：

#include<bits/stdc++.h>

using namespace std;

int vis[10005]; // vis[i]代表第 i天是否有商品在卖

int a[10005][2]; //a[i][0] 商品利润 a[i][1] 商品到期时间

int main()

{

int n;

scanf("%d",&n);

memset(vis,0,sizeof(vis));

for(int i=0;i<n;i++){

scanf("%d%d",&a[i][0],&a[i][1]);

}

for(int i=0;i<n;i++){

for(int j=i+1;j<n;j++){

if(a[i][0]<a[j][0]){ //排序，按润从大到小排序

swap(a[i][0],a[j][0]);

swap(a[i][1],a[j][1]);

}

}

}

int sum=0;

for(int i=0;i<n;i++){

for(int j=a[i][1];j>=1;j--){ //在截止日期之前卖出就行

if(vis[j]) //如果 j 天有商品在卖，查找前一天

continue;

vis[j]=1; //标识第 j 天卖 该商品

sum+=a[i][0]; //累加利润

break;

}

}

printf("%d\n",sum);

return 0;

}