贪心介绍

定义

贪心，指的是决策时都采取当前最优解的算法。
可以通过局部最优解拓展得到全局最优解。

用处

寻找最优解（如：找最大(小)值）

贪心类别

一、排序型贪心

这种类型就是通过给数据排序，不同的排序方法演绎下去就会有不同的答案ans。
然后要比较所有排序方法，选让这些ans的最值。

• 为什么会想到排序？

  虽然我们只看重眼前利益选择当前的最优解，随时准备开冲去比较两者选获利最大的【指直接从头开始遍历然后选择】。

  但这个时候我们暂且压一下枪理智一下：我们怎么知道我们现在选的是不是最优解呢？
  也就是说，可能现在这两个中，我选了一个当前最优解，但实际上跟后面比起来，这两个都不是最优解。
  也就是著名的苏格拉底的“拣麦穗的故事”。

  所以我们以全局眼光来看这些数据，飞到这片麦田之上，就会发现：“哦~原来利益最大的在那个地方、第二大的又在另个地方……”
  然后我们知道这些获利最大的点在哪里，就用原力把他们放到我们面前来，然后直接取走就行了。
  或者说：我们先辛苦一下对这些数据排下序，然后直接取最优结果就可以了。

所以我们就能得到有关排序型贪心的定义：

通过对数据，按照某种决策条件排序，使得任意两项均满足该决策条件，而找到最优解。

实现方法

1. 根据题意，分析每种状态的ans如何计算，以及题目要求取ans的什么最值。
2. 采用邻项交换排序思想，选取相邻两项$i,i+1$，比较两种状态的ans，选择最优的ans。由此可以推出一种基于数据比较的决策方案。
3. 按照该决策方案排序，算出排序后状态的ans值，即为结果。

邻项交换排序

这一部分请查看邻项交换排序笔记。

二、反悔型贪心

依然是上面的引例：

【我管不了那么多了我现在就要开冲.jpg……

但一路冲下去，如果发现有比之前选择的更好的数据，
我们是不是就会觉得后悔，觉得如果之前不选那个而选这个该多好。

因此我们就可以从之前所选择的当中，取一个最差的，然后跟这个最好的换一下。

这就是反悔贪心法的基本思路：

无论当前的选项是否最优都先接受，然后继续往后进行比较。
如果发现有比之前选择更优的，则反悔，舍弃之前最差的换成这个选项；否则继续往后比较。直到序列遍历完。

• 要记录之前所选择的，则一般采用优先队列。