【算法学习笔记】贪心算法

版权声明：本文为博主原创文章，转载请注明出处http://blog.csdn.net/u013132758。 https://blog.csdn.net/u013132758/article/details/50937499

1、什么是贪心算法

贪心也就是贪婪，就好比我们考试期末成绩是由平时分和期末成绩两部分组成，我们复习时肯定是想要在考完当前这门之后的最短的时间内得到最多的分数。这就是贪心的思想。

  所谓贪心算法就是指：我们所做出的选择在当前情况下总是最好的，它考虑的不是全局最优解，而是某种意义上的局部最优解。核心思想就是以局部最优解得到全局最优解。（需要注意的是贪心算法不是所有问题的全局最优解）

还有使用贪心策略必须要求满足无后效性（某个状态以后的过程不会影响以前的状态，只与当前状态有关）。

2、贪心算法的基本思路

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

    2.用分治的思想把求解的问题分成若干个子问题。

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

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

3、贪心算法适合的问题

贪心算法适合的条件必须满足下面条件：

1、贪心选择性质：就是指问题的整体最优解可以由局部最优解来得到，即通过贪心选择来得到。这是贪心算法与动态规划的本质区别。

2、最优子结构：所谓最优子结构是指问题的最优解包涵其子问题的最优解。最优子结构性质是使用贪心算法与动态规划的关键特征。

4、贪心算法实现的过程（贪心算法的框架）

ｗｈｉｌｅ（能朝总目标前进一步）

｛

利用贪心策略，求出可行解的一个解元素：

｝

由所有解元素组合成问题的可行解。

５、贪心算法的介绍

背包问题

有一个背包，背包容量是M=180。有7个物品，物品可以分割成任意大小。要求尽可能让装入背包中的物品总价值最大，但不能超过总容量。

物品 　　　　A　 　B　 C 　D 　　E 　F　 　G

重量（ｗ） 　35 　30 　60 　50 　40 　10 　25

价值 （ｐ）　10 　40 　30　 50 　35 　40 　30

问题分析：

目标函数： ∑pi最大

约束条件是装入的物品总重量不超过背包容量：∑wi<=M( M=180)。

（1）根据贪心的策略，每次挑选价值最大的物品装入背包，得到的结果是否最优？

（2）每次挑选所占重量最小的物品装入是否能得到最优解？

（3）每次选取单位重量价值最大的物品，成为解本题的策略。

值得注意的是，贪心算法并不是完全不可以使用，贪心策略一旦经过证明成立后，它就是一种高效的算法。

贪心算法还是很常见的算法之一，这是由于它简单易行，构造贪心策略不是很困难。

一般来说，贪心算法的证明围绕着：整个问题的最优解一定由在贪心策略中存在的子问题的最优解得来的。

对于背包问题中的3种贪心策略，都是无法成立（无法被证明）的。关于背包问题的最优解，我们采用动态规划的算法。下一篇文章我将介绍动态规划。

还需要说明的是，如果包裹是可以拆分的，那这个问题就得到了整体最优解，前面不变，就是当最后一次装进去已经超过容量的时候可以选择只装她的一部分！很多编程题一般是这种情况！

６、贪心算法常用的几大问题

１、找零钱

在贪心算法里面最常见的莫过于找零钱的问题了，题目大意如下，对于人民币的面值有1元 5元 10元 20元 50元 100元，下面要求设计一个程序，输入找零的钱，输出找钱方案中最少张数的方案，比如123元，最少是1张100的，1张20的，3张1元的，一共5张！

２、数字组合问题

设有N个正整数，现在需要你设计一个程序，使他们连接在一起成为最大的数字，例3个整数 12,456,342 很明显是45634212为最大，4个整数 342，45,7,98显然为98745342最大

３、活动时间安排的问题

    设有N个活动时间集合，每个活动都要使用同一个资源，比如说会议场，而且同一时间内只能有一个活动使用，每个活动都有一个使用活动的开始si和结束时间fi，即他的使用区间为（si,fi）,现在要求你分配活动占用时间表，即哪些活动占用该会议室，哪些不占用，使得他们不冲突，要求是尽可能多的使参加的活动最大化，即所占时间区间最大化！

上图为每个活动的开始和结束时间，我们的任务就是设计程序输出哪些活动可以占用会议室！

４、线段覆盖问题（我认为本质上和时间问题差不多）

在一维空间中告诉你N条线段的起始坐标与终止坐标，要求求出这些线段一共覆盖了多大的长度。

关于以上问题的解及代码，我就不写了，我认为这篇写的比我好：

http://blog.csdn.net/effective_coder/article/details/8736718