为什么贪心算法可用于解决最优化问题

最优化问题是程序设计中一类非常重要的问题。每一个最优化问题都包含一组约束条件和一个优化函数，满足约束条件的问题求解方案称为问题的可行解，使优化函数取得最优值的可行解称为问题的最优解。贪婪算法是解决最优化问题的一种基本方法。

它采用逐步构造最优解的思想，在问题求解的每一个阶段，都作出一个在一定标准下看上去最优的决策；决策一旦作出，就不可再更改。制定决策的依据称为贪婪准则。

　算法（Algorithm）是一系列解决问题的清晰指令，也就是说，能够对一定规范的输入，在有限时间内获得所要求的输出。如果一个算法有缺陷，或不适合于某个问题，执行这个算法将不会解决这个问题。不同的算法可能用不同的时间、空间或效率来完成同样的任务。一个算法的优劣可以用空间复杂度与时间复杂度来衡量。

算法可以理解为有基本运算及规定的运算顺序所构成的完整的解题步骤。或者看成按照要求设计好的有限的确切的计算序列，并且这样的步骤和序列可以解决一类问题。

一个算法应该具有以下五个重要的特征：

1、有穷性： 一个算法必须保证执行有限步之后结束；

2、确切性： 算法的每一步骤必须有确切的定义；

3、输入：一个算法有0个或多个输入，以刻画运算对象的初始情况，所谓0个输入是指算法本身定除了初始条件；

4、输出：一个算法有一个或多个输出，以反映对输入数据加工后的结果。没有输出的算法是毫无意义的；

5、可行性： 算法原则上能够精确地运行，而且人们用笔和纸做有限次运算后即可完成。

计算机科学家尼克劳斯-沃思曾著过一本著名的书《数据结构十算法= 程序》，可见算法在计算机科学界与计算机应用界的地位。 [编辑本段]算法的复杂度同一问题可用不同算法解决，而一个算法的质量优劣将影响到算法乃至程序的效率。算法分析的目的在于选择合适算法和改进算法。一个算法的评价主要从时间复杂度和空间复杂度来考虑。

时间复杂度

算法的时间复杂度是指算法需要消耗的时间资源。一般来说，计算机算法是问题规模n 的函数f(n)，算法的时间复杂度也因此记做

T(n)=Ο(f(n))

因此，问题的规模n 越大，算法执行的时间的增长率与f(n) 的增长率正相关，称作渐进时间复杂度（Asymptotic Time Complexity）。

空间复杂度

算法的空间复杂度是指算法需要消耗的空间资源。其计算和表示方法与时间复杂度类似，一般都用复杂度的渐近性来表示。同时间复杂度相比，空间复杂度的分析要简单得多。

详见百度百科词条"算法复杂度" [编辑本段]算法设计与分析的基本方法1递推法

递推法是利用问题本身所具有的一种递推关系求问题解的一种方法。它把问题分成若干步，找出相邻几步的关系，从而达到目的，此方法称为递推法。

2递归

递归指的是一个过程：函数不断引用自身，直到引用的对象已知

3穷举搜索法

穷举搜索法是对可能是解的众多候选解按某种顺序进行逐一枚举和检验，并从众找出那些符合要求的候选解作为问题的解。

4贪婪法

贪婪法是一种不追求最优解，只希望得到较为满意解的方法。贪婪法一般可以快速得到满意的解，因为它省去了为找最优解要穷尽所有可能而必须耗费的大量时间。贪婪法常以当前情况为基础作最优选择，而不考虑各种可能的整体情况，所以贪婪法不要回溯。

5分治法

把一个复杂的问题分成两个或更多的相同或相似的子问题，再把子问题分成更小的子问题……直到最后子问题可以简单的直接求解，原问题的解即子问题的解的合并。

6动态规划法

动态规划是一种在数学和计算机科学中使用的，用于求解包含重叠子问题的最优化问题的方法。其基本思想是，将原问题分解为相似的子问题，在求解的过程中通过子问题的解求出原问题的解。动态规划的思想是多种算法的基础，被广泛应用于计算机科学和工程领域。

7迭代法

迭代是数值分析中通过从一个初始估计出发寻找一系列近似解来解决问题（一般是解方程或者方程组）的过程，为实现这一过程所使用的方法统称为迭代法。 [编辑本段]算法分类算法可大致分为基本算法、数据结构的算法、数论与代数算法、计算几何的算法、图论的算法、动态规划以及数值分析、加密算法、排序算法、检索算法、随机化算法、并行算法。

算法可以宏泛的分为三类：

有限的，确定性算法 这类算法在有限的一段时间内终止。他们可能要花很长时间来执行指定的任务，但仍将在一定的时间内终止。这类算法得出的结果常取决于输入值。

有限的，非确定算法 这类算法在有限的时间内终止。然而，对于一个（或一些）给定的数值，算法的结果并不是唯一的或确定的。

无限的算法 是那些由于没有定义终止定义条件，或定义的条件无法由输入的数据满足而不终止运行的算法。通常，无限算法的产生是由于未能确定的定义终止条件。

贪心是人类自带的能力，贪心算法是在贪心决策上进行统筹规划的统称。

比如一道常见的算法笔试题---- 跳一跳 ：

我们自然而然能产生一种解法：尽可能的往右跳，看最后是否能到达。

本文即是对这种贪心决策的介绍。

狭义的贪心算法指的是解最优化问题的一种特殊方法，解决过程中总是做出当下最好的选择，因为具有最优子结构的特点，局部最优解可以得到全局最优解；这种贪心算法是动态规划的一种特例。 能用贪心解决的问题，也可以用动态规划解决。

而广义的贪心指的是一种通用的贪心策略，基于当前局面而进行贪心决策。以 跳一跳 的题目为例：

我们发现的题目的核心在于 向右能到达的最远距离 ，我们用maxRight来表示；

此时有一种贪心的策略：从第1个盒子开始向右遍历，对于每个经过的盒子，不断更新maxRight的值。

贪心的思考过程类似动态规划，依旧是两步： 大事化小 ， 小事化了 。

大事化小：

一个较大的问题，通过找到与子问题的重叠，把复杂的问题划分为多个小问题；

小事化了：

从小问题找到决策的核心，确定一种得到最优解的策略，比如跳一跳中的 向右能到达的最远距离 ；

在证明局部的最优解是否可以推出全局最优解的时候，常会用到数学的证明方式。

如果是动态规划：

要凑出m元，必须先凑出m-1、m-2、m-5、m-10元，我们用dp[i]表示凑出i元的最少纸币数；

有 dp[i]=min(dp[i-1], dp[i-2], dp[i-5], dp[i-10]) + 1 ;

容易知道 dp[1]=dp[2]=dp[5]=dp[10]=1 ；

根据以上递推方程和初始化信息，可以容易推出dp[1~m]的所有值。

似乎有些不对？ 平时我们找零钱有这么复杂吗？

从贪心算法角度出发，当m>10且我们有10元纸币，我们优先使用10元纸币，然后再是5元、2元、1元纸币。

从日常生活的经验知道，这么做是正确的，但是为什么？

假如我们把题目变成这样，原来的策略还能生效吗？

接下来我们来分析这种策略：

已知对于m元纸币，1，2，5元纸币使用了a，b，c张，我们有a+2b+5c=m；

假设存在一种情况，1、2、5元纸币使用数是x，y，z张，使用了更少的5元纸币（z<c），且纸币张数更少（x+y+z<a+b+c），即是用更少5元纸币得到最优解。

我们令k=5(c-z)，k元纸币需要floor(k/2)张2元纸币，k%2张1元纸币；（因为如果有2张1元纸币，可以使用1张2元纸币来替代，故而1元纸币只能是0张或者1张）

容易知道，减少(c-z)张5元纸币，需要增加floor(5(c-z)/2)张2元纸币和(5(c-z))%2张纸币，而这使得x+y+z必然大于a+b+c。

由此我们知道不可能存在使用更少5元纸币的更优解。

所以优先使用大额纸币是一种正确的贪心选择。

对于1、5、7元纸币，比如说要凑出10元，如果优先使用7元纸币，则张数是4；（1+1+1+7）

但如果只使用5元纸币，则张数是2；（5+5）

在这种情况下，优先使用大额纸币是不正确的贪心选择。（但用动态规划仍能得到最优解）

如果是动态规划：

前i秒的完成的任务数，可以由前面1~i-1秒的任务完成数推过来。

我们用 dp[i]表示前i秒能完成的任务数 ；

在计算前i秒能完成的任务数时，对于第j个任务，我们有两种决策：

1、不执行这个任务，那么dp[i]没有变化；

2、执行这个任务，那么必须腾出来(Sj, Tj)这段时间，那么 dp[i] = max(dp[i], dp[ S[j] ] ) + 1 ；

比如说对于任务j如果是第5秒开始第10秒结束，如果i>=10，那么有 dp[i]=max(dp[i], dp[5] + 1)； （相当于把第5秒到第i秒的时间分配给任务j）

再考虑贪心的策略，现实生活中人们是如何安排这种多任务的事情？我换一种描述方式：

我们自然而然会想到一个策略： 先把结束时间早的兼职给做了！

为什么？

因为先做完这个结束时间早的，能留出更多的时间做其他兼职。

我们天生具备了这种优化决策的能力。

这是一道 LeetCode题目 。

这个题目不能直接用动态规划去解，比如用dp[i]表示前i个人需要的最少糖果数。

因为（前i个人的最少糖果数）这种状态表示会收到第i+1个人的影响，如果a[i]>a[i+1]，那么第i个人应该比第i+1个人多。

即是 这种状态表示不具备无后效性。

如果是我们分配糖果，我们应该怎么分配？

答案是： 从分数最低的开始。

按照分数排序，从最低开始分，每次判断是否比左右的分数高。

假设每个人分c[i]个糖果，那么对于第i个人有 c[i]=max(c[i-1],c[c+1])+1 ; （c[i]默认为0，如果在计算i的时候,c[i-1]为0，表示i-1的分数比i高）

但是，这样解决的时间复杂度为 O(NLogN) ，主要瓶颈是在排序。

如果提交，会得到 Time Limit Exceeded 的提示。

我们需要对贪心的策略进行优化：

我们把左右两种情况分开看。

如果只考虑比左边的人分数高时，容易得到策略：

从左到右遍历，如果a[i]>a[i-1]，则有c[i]=c[i-1]+1；否则c[i]=1。

再考虑比右边的人分数高时，此时我们要从数组的最右边，向左开始遍历：

如果a[i]>a[i+1], 则有c[i]=c[i+1]+1；否则c[i]不变；

这样讲过两次遍历，我们可以得到一个分配方案，并且时间复杂度是 O(N) 。

题目给出关键信息：1、两个人过河，耗时为较长的时间；

还有隐藏的信息：2、两个人过河后，需要有一个人把船开回去；

要保证总时间尽可能小，这里有两个关键原则： 应该使得两个人时间差尽可能小（减少浪费），同时船回去的时间也尽可能小（减少等待）。

先不考虑空船回来的情况，如果有无限多的船，那么应该怎么分配？

答案： 每次从剩下的人选择耗时最长的人，再选择与他耗时最接近的人。

再考虑只有一条船的情况，假设有A/B/C三个人，并且耗时A<B<C。

那么最快的方案是：A+B去, A回；A+C去；总耗时是A+B+C。（因为A是最快的，让其他人来回时间只会更长， 减少等待的原则 ）

如果有A/B/C/D四个人，且耗时A<B<C<D，这时有两种方案：

1、最快的来回送人方式，A+B去；A回；A+C去，A回；A+D去； 总耗时是B+C+D+2A （减少等待原则）

2、最快和次快一起送人方式，A+B先去，A回；C+D去，B回；A+B去；总耗时是 3B+D+A （减少浪费原则）

对比方案1、2的选择，我们发现差别仅在A+C和2B；

为何方案1、2差别里没有D？

因为D最终一定要过河，且耗时一定为D。

如果有A/B/C/D/E 5个人，且耗时A<B<C<D<E，这时如何抉择？

仍是从最慢的E看。（参考我们无限多船的情况）

方案1，减少等待；先送E过去，然后接着考虑四个人的情况；

方案2，减少浪费；先送E/D过去，然后接着考虑A/B/C三个人的情况；（4人的时候的方案2）

到5个人的时候，我们已经明显发了一个特点：问题是重复，且可以由子问题去解决。

根据5个人的情况，我们可以推出状态转移方程 dp[i] = min(dp[i - 1] + a[i] + a[1], dp[i - 2] + a[2] + a[1] + a[i] + a[2]);

再根据我们考虑的1、2、3、4个人的情况，我们分别可以算出dp[i]的初始化值：

dp[1] = a[1];

dp[2] = a[2];

dp[3] = a[2]+a[1]+a[3];

dp[4] = min(dp[3] + a[4] + a[1], dp[2]+a[2]+a[1]+a[4]+a[2]);

由上述的状态转移方程和初始化值，我们可以推出dp[n]的值。

贪心的学习过程，就是对自己的思考进行优化。

是把握已有信息，进行最优化决策。

这里还有一些收集的 贪心练习题 ，可以实践练习。

这里 还有在线分享，欢迎报名。

以上就是关于为什么贪心算法可用于解决最优化问题全部的内容，包括:为什么贪心算法可用于解决最优化问题、都说程序执行的效率跟算法有关，究竟什么是计算机的算法呢怎么理解的怎么使用、程序员算法基础——贪心算法等相关内容解答，如果想了解更多相关内容，可以关注我们，你们的支持是我们更新的动力！