贪心算法

贪心算法（又称贪婪算法）是指，在对问题求解时，总是做出在当前看来是最好的选择。

也就是说，不从整体最优上加以考虑，他所做出的是在某种意义上的局部最优解。

贪心算法不是对所有问题都能得到整体最优解，关键是贪心策略的选择，选择的贪心策略必须具备无后效性，即某个状态以前的过程不会影响以后的状态，只与当前状态有关。

基本要素

贪心选择

贪心选择是指所求问题的整体最优解可以通过一系列局部最优的选择，即贪心选择来达到。

这是贪心算法可行的第一个基本要素，也是贪心算法与动态规划算法的主要区别。

贪心选择是采用从顶向下、以迭代的方法做出相继选择，每做一次贪心选择就将所求问题简化为一个规模更小的子问题。

对于一个具体问题，要确定它是否具有贪心选择的性质，我们必须证明每一步所作的贪心选择最终能得到问题的最优解。

通常可以首先证明问题的一个整体最优解，是从贪心选择开始的，而且作了贪心选择后，原问题简化为一个规模更小的类似子问题。

然后，用数学归纳法证明，通过每一步贪心选择，最终可得到问题的一个整体最优解。

最优子结构

当一个问题的最优解包含其子问题的最优解时，称此问题具有最优子结构性质。

运用贪心策略在每一次转化时都取得了最优解。

问题的最优子结构性质是该问题可用贪心算法或动态规划算法求解的关键特征。

贪心算法的每一次操作都对结果产生直接影响，而动态规划则不是。

贪心算法对每个子问题的解决方案都做出选择，不能回退；动态规划则会根据以前的选择结果对当前进行选择，有回退功能。

动态规划主要运用于二维或三维问题，而贪心一般是一维问题。

跳跃游戏 II

https://leetcode.com/problems/jump-game-ii/

题目

给定一个非负整数数组，你最初位于数组的第一个位置。

数组中的每个元素代表你在该位置可以跳跃的最大长度。

你的目标是使用最少的跳跃次数到达数组的最后一个位置。

示例:

输入: [2,3,1,1,4]
输出: 2
解释: 跳到最后一个位置的最小跳跃数是 2。
     从下标为 0 跳到下标为 1 的位置，跳 1 步，然后跳 3 步到达数组的最后一个位置。

说明:

假设你总是可以到达数组的最后一个位置。

思考过程

看到这道题，你的第一反应是怎么解决呢？

我甚至产生了要使用 DP 去解题的思路，不过后来一想也不对，这题不需要回退，而且是一道一维问题。

所以就想到了贪心算法。

那应该怎么使用贪心呢？

思路1

有一句话叫做以终为始，就是我们从后往前遍历。

找到一个可以可以达到结尾 i_n 的地方，如果有多个，就选择距离最远的那一个 i_n-1。

然后找到可以达到 i_n-1 最远的地方 i_n-2。

依次类推，找到最初的位置。

java 实现

public int jump(int[] nums) {
    int count = 0;
    if(nums.length == 1) {
        return count;
    }
    // 最後一個位置。
    for(int i = nums.length-1; i > 0; i--) {
        // 取出当前位置的值
        // 从前往后循环都一样，因为你必须循环一遍，才能找到最大的那一个元素。
        // 最后前面的一个元素，肯定可以达到，至少为 1 步
        // 从前向后，记录肯定是最远的。
        for(int j = 0; j < i; j++) {
            // 哪一个值并不重要，重要的是距离
            int len = i - j;
            int maxLen = nums[j];
            // 可以达到
            if(maxLen >= len && len > 1) {
                i -= (len-1);
                break;
            }
        }
        // 次数递增
        count++;
    }
    return count;
}

理论上这个复杂度是比较高的，不过我的执行结果却是双 100。

Runtime: 0 ms, faster than 100.00% of Java online submissions for Jump Game II.
Memory Usage: 36.3 MB, less than 100.00% of Java online submissions for Jump Game II.

为了避免错判，我跑了 2 次，结果都是超过双百。:)

最坏的场景就是全部都是 1，时间复杂度为 O(n^2)。

思路 2

最基本的思路，可能是从前往后遍历。

以 [2,3,1,1,4] 作为例子。

我们第一次可以选择走两步：

（1）直接两步，可以走到 1，

（2）走一步，选择走到3，然后向后走走3步。

如果用贪心的角度思考的话，肯定是方案 2 划算一点。

然后我们一直按照这个方式，走到最后。

其中方案（2）能走的最远的地方，我们可以定义为边界。

java 实现

最核心的就是一句话，如何达到可以达到的最远距离呢？

public int jump(int[] nums) {
    int count = 0;
    if(nums.length == 1) {
        return count;
    }
    // 目前能跳到的最远位置
    int maxFar = 0;
    // 上次跳跃可达范围右边界（下次的最右起跳点）
    int end = 0;
    // 最后一个位置不需要访问。
    for(int i = 0; i < nums.length-1; i++) {
        maxFar = Math.max(maxFar, i + nums[i]);
        // 到达上次跳跃能到达的右边界了
        if(i == end) {
            // 更新右边界
            end = maxFar;
            count++;
        }
    }
    return count;
}

當然，這個性能也是很好的：

Runtime: 0 ms, faster than 100.00% of Java online submissions for Jump Game II.
Memory Usage: 36.7 MB, less than 100.00% of Java online submissions for Jump Game II.

区间调度问题

假设有如下课程，希望尽可能多的将课程安排在一间教室里：

课程 开始时间 结束时间
美术 9AM 10AM
英语 9:30AM 10:30AM
数学 10AM 11AM
计算机 10:30AM 11:30AM
音乐 11AM 12PM

这个问题看似要思考很多，实际上算法很简单:

1.选择结束最早的课，便是要在这教室上课的第一节课

2.接下来，选择第一堂课结束后才开始的课，并且结束最早的课，这将是第二节在教室上的课。

重复这样做就能找出答案，这边的选择策略便是结束最早且和上一节课不冲突的课进行排序，因为每次都选择结束最早的，所以留给后面的时间也就越多，自然就能排下越多的课了。

每一节课的选择都是策略内的局部最优解(留给后面的时间最多)，所以最终的结果也是近似最优解(这个案例上就是最优解)。

背包问题

有一个背包，容量为35磅， 现有如下物品

物品 重量 价格
吉他 15 1500
音响 30 3000
笔记本电脑 20 2000
显示器 29 2999
笔 1 200

要求达到的目标为装入的背包的总价值最大，并且重量不超出。

方便计算所以只有3个物品，实际情况可能是成千上万。

同上使用贪婪算法，因为要总价值最大，所以每次每次都装入最贵的,然后在装入下一个最贵的，选择结果如下：

选择: 音响 + 笔，总价值 3000 + 200 = 3200

并不是最优解: 吉他 + 笔记本电脑, 总价值 1500 + 2000 = 3500

当然选择策略有时候并不是很固定，可能是如下：

(1)每次挑选价值最大的,并且最终重量不超出：

选择: 音响 + 笔，总价值 3000 + 200 = 3200

(2)每次挑选重量最大的,并且最终重量不超出(可能如果要求装入最大的重量才会优先考虑)：

选择: 音响 + 笔，总价值 3000 + 200 = 3200

(3)每次挑选单位价值最大的(价格/重量),并且最终重量不超出：

选择: 笔+ 显示器，总价值 200 + 2999 = 3199

如上最终的结果并不是最优解，在这个案例中贪婪算法并无法得出最优解，只能得到近似最优解,也算是该算法的局限性之一。

该类问题中需要得到全局最优解的话可以采取动态规划算法。

参考资料

百度百科-贪心算法

那些经典算法：贪心算法

五大常用算法：分治、动态规划、贪心、回溯和分支界定详解

算法(六):图解贪婪算法