讲解一下贪心算法

“好事”文章分享

Go语言学习1-基础入门 作者：huazie

这篇文章介绍了Go语言的基础入门知识，包括环境变量的配置、安装目录的介绍、工作区的设置、源码文件的分类、代码包的使用和初始化等内容。文章还提供了详细的命令和工具的使用说明，帮助初学者快速掌握Go语言的基本操作。

贪心算法

所谓贪心算法，就是指它的每一步计算作出的都是在当前看起来最好的选择，也就是说它所作出的选择只是在某种意义上的局部最优选择，并不从整体最优考虑。在这里，我把这两种选择的思路称作局部最优解和整体最优解。

因此，我们可以得到贪心算法的基本思路：

1. 根据问题来建立数学模型，一般面试题会定义一个简单模型；
2. 把待求解问题划分成若干个子问题，对每个子问题进行求解，得到子问题的局部最优解；
3. 把子问题的局部最优解进行合并，得到最后基于局部最优解的一个解，即原问题的答案。

案例一

N个苹果，用6号袋和8号袋装，分别能装6个和8个苹果 必须装满每个袋子，最少需要多少个袋子才能装满？ 无法满足要求的话，返回-1；

局部最优思路

N个苹果，咱们直觉是，拿大号袋子，装，尽可能1个袋子，装更多的苹果，这样袋子数量少 但是呢？ 就像N=12一样，你先装8号，还剩4个，找不到袋子装 只能考虑8号袋子来0个，所以剩下的12个用6号袋子装，至少2个 如果N=7这种，8和6依次都没法装，不好意思，那就返回-1

不妨设需要k8个8号袋子，k6个6号袋子，自然先装8号袋子

（1）默认最开始k8=k6=-1，暂时都不符合条件

（2）先装8号袋子：k8=N/8

（3）那还余下M=N-8*k8个苹果，剩下的只能用6号袋子来装，那如果M%6=0就可以装，直接返回k6+k8；否则需要尝试新的k8

（4）如果（3）没法装的话（即M%6!=0），则让k8–，即8号袋子少拿一个，然后回（3）

（5）如果直到k8=0了，k6仍然没法装，那不好意思，整体就装不下了。

/**
 * N个苹果，用6号袋和8号袋装，分别能装6个和8个苹果
 * 必须装满每个袋子，最少需要多少个袋子才能装满？
 * 无法满足要求的话，返回-1
 */
@Slf4j
public class GreedyTest {
    public static void main(String[] args) {
        int n = 12;
        log.info("result = {}", greedy(n));
    }

    public static int greedy(int n) {
        // 最大8个果子的袋子数量
        int c6 = -1;
        int c8 = -1;
        c8 = n / 8;
        //余数
        int m = n - c8 * 8;
        while ( c8 >= 0 && m >= 0) {
            if (m % 6 == 0) {
                // 说明够袋子装了，可以退出
                c6 = m / 6;
                break;
            } else {
                // 让最大袋子数量-1，继续动态计算
                c8--;
                m = n - c8 * 8;
            }
        }


        return c6 > -1 ? (c6+c8): -1;
    }
}

牺牲一点当前利益：装8个袋子数量-1，牺牲一些利益。

贪心算法的局限性

从上面这个例子我们可以看出，如果只是简单采用贪心的思路，容易进入死胡同。

这就是贪心算法所谓的局部最优导致的问题，因为我们每一步都尽量多地使用容量最大的袋子，因为这样数量肯定最小，但是有的时候我们就进入了死胡同。

所谓局部最优，就是只考虑“当前”的最大利益，既不向前多看一步，也不向后多看一步，导致每次都只用当前阶段的最优解。

那么如果纯粹采用这种策略我们就永远无法达到整体最优，也就无法求得题目的答案了。至于能得到答案的情况那就是我们走狗屎运了。

虽然纯粹的贪心算法作用有限，但是这种求解局部最优的思路在方向上肯定是对的，毕竟所谓的整体最优肯定是从很多个局部最优中选择出来的，因此所有最优化问题的基础都是贪心算法。