贪婪算法详解(思想步骤以及经典例子)

贪婪算法是五大常用算法之一，需要掌握，本文会详细介绍贪婪算法的基本思想及其代码实现例子@mikechen

贪婪算法定义

贪婪算法，英文名为Greedy Algorithm，又名贪心算法。

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

 

贪婪算法原理思想

贪婪算法的基本思路，主要分为如下三步：

步骤1：从某个初始解出发；

步骤2：采用迭代的过程，当可以向目标前进一步时，就根据局部最优策略，得到一部分解，缩小问题规模；

步骤3：将所有解综合起来。

 

贪婪算法的应用场景

简单地说，问题能够分解成子问题来解决，子问题的最优解能递推到最终问题的最优解，就可以使用贪婪算法。

比如：贪婪算法可以解决一些最优化问题，如：求图中的最小生成树，求哈夫曼编码等。

 

 

贪婪算法经典例子

1.找零钱的例子

1）题目

指定币值和相应的数量，用最少的数量凑齐某金额。

 

2）思路

利用贪婪算法，基本思路：我们优先选择面值大的钱币，以此类推，直到凑齐总金额。

 

3）算法实现

 

2.活动选择例子

1）题目

有这么一堆数，按照金字塔排列下来，如下图所示：

我们从顶点开始，求从顶部到底部的最大路径之和。

 

2）思路

利用贪婪算法，基本思路：要是用眼瞅，比较容易能看出来最佳路径是9-7-3-4-5，但是如果数一多，眼瞅就不好使了，此时就得靠代码去算。

 

3）算法实现

// 注意，下面的代码只是表意，不能直接扒过去用
// a[i][j]表示数组，maxJ表示数组的最大层数，temp表示临时数值
// maxJ表示总列数，maxI表示当前列的最大行数
 
for(j=0; j<maxJ; j++){
    for(i=0; i<maxI; i++){
        temp1 = a[i][j] + a[i][j+1];
        temp2 = a[i][j] + a[i+1][j+1];
        temp = max(temp1, temp2);
    }
    maxSum = maxSum + temp;
}
return maxSum;

 

陈睿mikechen

10年+大厂架构经验，资深技术专家，就职于阿里巴巴、淘宝、百度等一线互联网大厂。

关注「mikechen」公众号，获取更多技术干货！

后台回复【面试】即可获取《史上最全阿里Java面试题总结》，后台回复【架构】，即可获取《阿里架构师进阶专题全部合集》