常用算法总结之贪心算法

贪心算法思想

贪心算法就是这样的算法，它在每一步都做出当时看起来最佳的选择。也就是说它总是做出局部最优的选择，寄希望这样的选择导致全局最优解。

贪心算法并不保证得到最优解，但很多问题确实可以求得最优解。

我们可以按如下步骤设计贪心算法：

将最优化问题转化为这样的形式：对其做出一次选择后，只剩下一个子问题需要求解。
证明做出贪心选择后，原问题总是存在最优解，即贪心选择总是安全的。
证明做出选择后，剩余的子问题满足性质：其最优解与贪心选择组合即可得到原问题的最优解，这样就得到了最优子结构。

贪心算法与动态规划的区别

0-1背包问题

一个正在抢劫商店的小偷，发现了n个商品，第i个商品价值v_i美元，重w_i磅，v_i和w_i都是整数。这个小偷希望拿走价值尽量高的商品，但他的背包最多能容纳W磅重的商品，W是一个整数。他应该拿哪些商品？（我们称这个问题为0-1背包问题，因为对每个商品，小偷要么把他完整拿走，要么把他留下；他不能只拿走商品的一部分，或者把一个商品拿走多次。）

分数背包问题

设定与0-1背包问题一样的，但对每个商品，小偷可以拿走其一部分。你可以将0-1背包中的商品想象为金锭，而分数背包问题中的商品更像金砂。

分析

我们可以用贪心策略解决分数背包问题。我们首先计算每个商品的每磅价值v_i/w_i。遵循贪心策略，小偷首先尽量多的拿走每磅价值最高的商品。如果此商品已经全部拿走而背包未满，他继续尽量多的拿走每磅价值第二高的商品，依此类推，直到达到重量上限W。

对于分数背包问题，上述贪心策略首先拿走每磅价值最大的商品，是可以生成最优解的。该策略对0-1背包无效是因为小偷无法装满背包，空闲空间降低了方案的有效每磅价值。

在0-1背包问题中，当我们考虑是否将一个商品加入背包时，必须比较包含此商品的子问题的解与不包含它的子问题的解，然后才能做出选择。这会导致大量的重叠子问题–动态规划的标识。这种问题就适合用动态规划去做。

分糖果问题

leetcode 135. Candy

public static int candy2(int[] ratings) {
        if (ratings.length == 0) {
            return 0;
        }
        int[] candies = new int[ratings.length];
        candies[0] = 1;
        for (int i = 1; i < ratings.length; i++) {
            if (ratings[i] > ratings[i - 1]) {
                candies[i] = candies[i - 1] + 1;
            } else {
                candies[i] = 1;
            }
        }
        int result = candies[ratings.length - 1];

        for (int i = ratings.length - 2; i >= 0; i--) {
            int temp = 1;
            if (ratings[i] > ratings[i + 1]) {
                temp = candies[i + 1] + 1;
            }
            candies[i] = Math.max(candies[i], temp);
            result += candies[i];
        }
        return result;
    }