概念详解#

贪心算法的定义：

贪心算法是指在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，只做出在某种意义上的局部最优解。贪心算法不是对所有问题都能得到整体最优解，关键是贪心策略的选择，选择的贪心策略必须具备无后效性，即某个状态以前的过程不会影响以后的状态，只与当前状态有关。

解题的一般步骤是：

1.建立数学模型来描述问题；

2.把求解的问题分成若干个子问题；

3.对每一子问题求解，得到子问题的局部最优解；

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

如果大家比较了解动态规划，就会发现它们之间的相似之处。最优解问题大部分都可以拆分成一个个的子问题，把解空间的遍历视作对子问题树的遍历，则以某种形式对树整个的遍历一遍就可以求出最优解，大部分情况下这是不可行的。贪心算法和动态规划本质上是对子问题树的一种修剪，两种算法要求问题都具有的一个性质就是子问题最优性(组成最优解的每一个子问题的解，对于这个子问题本身肯定也是最优的)。动态规划方法代表了这一类问题的一般解法，我们自底向上构造子问题的解，对每一个子树的根，求出下面每一个叶子的值，并且以其中的最优值作为自身的值，其它的值舍弃。而贪心算法是动态规划方法的一个特例，可以证明每一个子树的根的值不取决于下面叶子的值，而只取决于当前问题的状况。换句话说，不需要知道一个节点所有子树的情况，就可以求出这个节点的值。由于贪心算法的这个特性，它对解空间树的遍历不需要自底向上，而只需要自根开始，选择最优的路，一直走到底就可以了。

三个要点：

1. 贪心只保证”当前最优”，不保证”全局最优”。 一个贪心策略能不能用，必须经过严格证明（数学归纳法、交换论证等），凭感觉”显然正确”经常翻车。
2. 无后效性。 做了当前选择之后，问题的剩余部分不受”之前怎么选的”影响，只与当前状态有关——这正是贪心与 DP 的分界线：DP 需要回头看历史，贪心不用。
3. 贪心是 DP 的特例。 若每个状态的最优值只依赖当前状况、不需要知道子树的所有情况，DP 的”填表”就退化成”一条路走到底”的贪心。

话不多说，我们来看几个具体的例子慢慢理解它。

经典问题：活动选择#

活动选择问题是《算法导论》上的例子，也是一个非常经典的问题。有 n 个需要在同一天使用同一个教室的活动 a1,a2,…,an，教室同一时刻只能由一个活动使用。每个活动 ai 都有一个开始时间 si 和结束时间 fi。一旦被选择后，活动 ai 就占据半开时间区间 [si, fi)。如果 [si, fi) 和 [sj, fj) 互不重叠，ai 和 aj 两个活动就可以被安排在这一天。该问题就是要安排这些活动使得尽量多的活动能不冲突的举行。

哪些策略是错误的？ 直观上容易想到两个”看起来有道理”的做法，它们都不能得到最优解：

• 每次选择开始时间最早的活动：开始最早的活动可能持续非常久，占掉整间教室，导致其他活动全部无法安排；
• 每次选择持续时间最短的活动：最短的活动可能恰好横跨在两个”黄金时段”之间，破坏掉两场本可以安排的活动。

正确的贪心策略：每次选取结束时间最早的活动。 可以用数学归纳法证明。直观上也很好理解：按这种方法选择相容活动，能为未安排的活动留下尽可能多的时间。这也是把各项活动按照结束时间单调递增排序的原因——排序后，每次扫描到第一个”开始时间 ≥ 上一个已选活动结束时间”的活动就选它，一遍扫描即可。

求最大价值#

下面的代码演示了一个贪心枚举的统计思路：对每一种可能的”价格下限”，统计不低于该价格的客户数量，用 价格 × 人数 更新最大值。

1
package JUC;
2

3
import java.util.*;
4
import java.time.LocalDate;
5

6
public class Main {
7
    public static void main(String[] args) {
8
        Scanner scanner = new Scanner(System.in);
9
        int n = scanner.nextInt();
10
        int[] price = new int[n];
11
        int[] endPrice = new int[1001];
12
        int index = 0;
13
        for (int i = 0; i < n; i++) {
14
            price[i] = scanner.nextInt();
15
        }
16
        //从大到小排序
17
        Arrays.sort(price);
18
        for (int i = price[price.length-1]; i > 0 ; i--) {
19

20
            //统计大于改价格的客户的数量
21
            int sum = 0;
22
            for (int j = 0; j < n; j++) {
23
                if(price[j] >= i){
24
                    sum++;
25
                }
26

27
            }
28

29
            endPrice[index] = sum*i;
30
            index++;
31
        } System.out.println(Arrays.stream(endPrice).max().getAsInt());
32
    }
33
}