贪心算法最大值

㈠ 背包问题的贪心算法所需的计算时间为

背包问题的贪心算法所需的计算时间为0（nlogn）。

贪心算法的应用：

活动安排问题：

在活动安排问题中，需要在给定的时间内安排一系列活动，使得所有活动都能完成，并且总的耗时最短。贪心算法可以通过每次选择结束时间最早的活动来安排，以达到总耗时最短的目的。

最小生成树问题：

在最小生成树问题中，需要在给定的图中找到一个连接所有节点的最小边权和的树。贪心算法可以通过每次选择权值最小的边来连接节点，以达到最小边权和的目的。例如局部最优解能够导致全局最优解的问题。在实际应用中，需要根据具体问题的特点来选择合适的算法。

背包问题：

在背包问题中，需要在给定的背包容量下，选择一系列物品放入背包，使得总价值最大。贪心算法可以通过每次选择价值最大的物品放入背包，以达到总价值最大的目的。贪心算法并不适用于所有问题，它只能用于满足特定条件的问题。

㈡ 贪心思想

在学习数据结构的时候，我们已经见过了贪心思想在Prim和Kruskal中的完美应用，贪心思想因为其的简洁在算法中经常会被用到，有的时候在生活中，我们也会无意中使用到l贪心算法。比如在去shopping时，经常需要进行找零钱的过程，我们总是不自觉的先把大的找出来。

那么什么是贪心思想？

贪心算法总是作出在当前看来最好的选择，也就是说贪心算法并不从整体最优考虑，它所作出的选择只是在某种意义上的局部最优选择。

只有在满足最优子结构的情况下贪心算法得到的结果才是最优结果。

比如找钱的问题，我要给你一百，那么我尽可能每一次给你最多的。

或者比如磁盘的最优存储问题，所谓贪心选择性质是指所求问题的整体最优解可以通过一系列局部最优的选择，即贪心选择来达到。

Prim和kruskal算法都是每次选择最小的边纳入生成树。

所谓贪心选择性质是指所求问题的整体最优解可以通过一系列局部最优的选择，即贪心选择来达到。这也是贪心问题和动态规划问题的主要区别。

在n行m列的正整数矩阵中，要求从每一行中选一个数，使得选出的n个数的和最大。

可运用贪心策略，选n次，每一次选相应行中的最大值即可。

但是，在一个n*m的方格阵中，每一格子赋予一个数，规定每次移动时只能向上或向右，现试找出一条路径，使其从左下角至右上角所经过的权值之和最大。

同样考虑贪心策略，从左下角向右上角移动，每次移动选择权值较大的一个方向。

以2*3矩阵为例，采用贪心的策略得到的是1,3,4,6和为14但是实际的最优结果为1,2,100,6和为109.

所以说贪心算法并不是总是可行，证明当前问题存在贪心选择性质（全局最优解可以通过局部最优贪心选择达到）和最优子结构性质（问题的最优解包含了其子问题的最优解）。所以贪心问题如果当前的选择不会干扰之后的选择，则不会出现问题。

其他的情况就需要进行证明，证明的最好办法就是将最小子问题进行一步步的合并，直到最后还原为最后的原问题，若所得到的解是总体最优的则可以使用贪心思想，否则不可以。

比如上面的问题，我们的走一步的最优解为1，3，然后我们判断一次走两步的最优解是否任然为1,3这个路径，答案显然不是，变为 1,2,100这个路径，所以显然不能使用贪心思想。

假设1元、2元、5元、10元、20元、50元、100元的纸币分别有c0, c1, c2, c3, c4, c5, c6张。现在要用这些钱来支付K元，至少要用多少张纸币？用贪心算法的思想，很显然，每一步尽可能用面值大的纸币即可。在日常生活中我们自然而然也是这么做的。

有n个需要在同一天使用同一个教室的活动a1,a2,…,an，教室同一时刻只能由一个活动使用。每个活动ai都有一个开始时间si和结束时间fi 。一旦被选择后，活动ai就占据半开时间区间[si,fi)。如果[si,fi]和[sj,fj]互不重叠，ai和aj两个活动就可以被安排在这一天。该问题就是要安排这些活动使得尽量多的活动能不冲突的举行。

部分背包问题， 有n个物体，第i个物体重量为wi,价值为vi,在总重量不超过C的情况下，让总价值尽可能的高。每个物体都可以只取一部分。

我们可以考虑重量和价值的比值作为单价。

㈢ 贪心算法及其应用

求解一个问题时有多个步骤，每个步骤都选择当下最优的那个解，而不用考虑整体的最优解。通常，当我们面对的问题拥有以下特点的时候，就可以考虑使用贪心算法。

比如，我们举个例子，仓库里面总共有五种豆子，其对应的重量和总价值如下，现在我们有一个可以装100KG重量的袋子，怎么装才能使得袋子中的豆子价值最大？

我们首先看看这个问题是否符合贪心算法的使用场景？限制值是袋子100KG，期望值是袋子里面的价值最高。所以是符合的。那么我们尝试着应用下贪心算法的方法，每一个步骤都寻找当下的最优解，怎么做呢？

把仓库里面的每种豆子价值除以重量，得出每种豆子的单价，那么当下的最优解，肯定是尽可能最多地装单价最贵的，也就是先把20KG的黄豆都装上，然后再把30KG的绿豆都装上，再装50KG的红豆，那么此时正好装满袋子，总价值将是270元，这就是通过贪心算法求解的答案。

贪心算法的应用在这个问题上的求解是否是最优解需要一个很复杂的数学论证，我们不用那样，只要心里举几个例子，验证下是否比它更好即可，如果举不出例子，那么就可以认为这就是最优解了。

虽然贪心算法虽然在大部分实践场景中都能得到最优解，但是并不能保证一定是最优解。比如在如下的有向带权图中寻找从S到T的最短路径，那么答案肯定就是S->A->E->T，总代价为1+4+4=9；

然而，实际上的最短路径是S->B->D->T，总代价为6。

所以，不能所有这类问题都迷信贪心算法的求解，但其作为一种算法指导思想，还是很值得学习的。

除了以上袋子装豆子的问题之外，还有很多应用场景。这种问题能否使用贪心算法来解决的关键是你能否将问题转换为贪心算法适用的问题，即找到问题的限制值和期望值。

我们有m个糖果要分给n个孩子，n大于m，注定有的孩子不能分到糖果。其中，每个糖果的大小都不同，分别为S1,S2,S3...,Sm，每个孩子对糖果的需求也是不同的，为N1,N2,N3...,Nn，那么我们如何分糖果，才能尽可能满足最多数量孩子的需求？

这个问题中，限制值是糖果的数量m，期望值满足最多的孩子需求。对于每个孩子，能用小的糖果满足其需求，就不要用大的，避免浪费。所以我们可以给所有孩子的需求排个序，从需求最小的孩子开始，用刚好能满足他的糖果来分给他，以此来分完所有的糖果。

我们有1元、5元、10元、20元、50元、100元纸币各C1、C5、C10、C20、C50、C100张，现在要购买一个价值K元的东西，请问怎么才能适用最少的纸币？

这个问题应该不难，限制值是各个纸币的张数，期望值是适用最少的纸币。那么我们就先用面值最大的100元去付钱，当再加一张100元就超过K时，就更换小面额的，直至正好为K元。

对于n个区间[L1,R1],[L2,R2]...[Ln,Rn]，我们怎么从中选出尽可能多的区间，使它们不相交？

我们需要把这个问题转换为符合贪心算法特点的问题，假设这么多区间的最左端点是Lmin，最右端点是Rmax，那么问题就是在[Lmin,Rmax]中，选择尽可能多的区间往里面塞，并且保证它们不相交。这里，限制值就是区间[Lmin,Rmax]，期望值就是尽可能多的区间。

我们的解决办法就是每次从区间中选择那种左端点>=已经覆盖区间右边端点的，且该区间右端点尽可能高小的。如此，我们可以让未覆盖区间尽可能地大，才能保证可以塞进去尽可能多的区间。

贪心算法最重要的就是学会如何将要解决的问题抽象成适合贪心算法特点的模型，找到限制条件和期望值，只要做好这一步，接下来的就比较简单了。在平时我们不用刻意去记，多多练习类似的问题才是最有效的学习方法。

㈣ 程序员都应该精通的六种算法，你会了吗

对于一名优秀的程序员来说，面对一个项目的需求的时候，一定会在脑海里浮现出最适合解决这个问题的方法是什么，选对了算法，就会起到事半功倍的效果，反之，则可能会使程序运行效率低下，还容易出bug。因此，熟悉掌握常用的算法，是对于一个优秀程序员最基本的要求。

那么，常用的算法都有哪些呢？一般来讲，在我们日常工作中涉及到的算法，通常分为以下几个类型：分治、贪心、迭代、枚举、回溯、动态规划。下面我们来一一介绍这几种算法。

一、分治算法

分治算法，顾名思义，是将一个难以直接解决的大问题，分割成一些规模较小的相同问题，以便各个击破，分而治之。

分治算法一般分为三个部分：分解问题、解决问题、合并解。

分治算法适用于那些问题的规模缩小到一定程度就可以解决、并且各子问题之间相互独立，求出来的解可以合并为该问题的解的情况。

典型例子比如求解一个无序数组中的最大值，即可以采用分治算法，示例如下：

def pidAndConquer(arr,leftIndex,rightIndex):

if(rightIndex==leftIndex+1 || rightIndex==leftIndex){

return Math.max(arr[leftIndex],arr[rightIndex]);

}

int mid=(leftIndex+rightIndex)/2;

int leftMax=pidAndConquer(arr,leftIndex,mid);

int rightMax=pidAndConquer(arr,mid,rightIndex);

return Math.max(leftMax,rightMax);

二、贪心算法

贪心算法是指在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的仅是在某种意义上的局部最优解。

贪心算法的基本思路是把问题分成若干个子问题，然后对每个子问题求解，得到子问题的局部最优解，最后再把子问题的最优解合并成原问题的一个解。这里要注意一点就是贪心算法得到的不一定是全局最优解。这一缺陷导致了贪心算法的适用范围较少，更大的用途在于平衡算法效率和最终结果应用，类似于：反正就走这么多步，肯定给你一个值，至于是不是最优的，那我就管不了了。就好像去菜市场买几样菜，可以经过反复比价之后再买，或者是看到有卖的不管三七二十一先买了，总之最终结果是菜能买回来，但搞不好多花了几块钱。

典型例子比如部分背包问题：有n个物体，第i个物体的重量为Wi，价值为Vi，在总重量不超过C的情况下让总价值尽量高。每一个物体可以只取走一部分，价值和重量按比例计算。

贪心策略就是，每次都先拿性价比高的，判断不超过C。

三、迭代算法

迭代法也称辗转法，是一种不断用变量的旧值递推新值的过程。迭代算法是用计算机解决问题的一种基本方法，它利用计算机运算速度快、适合做重复性操作的特点，让计算机对一组指令(或一定步骤)进行重复执行，在每次执行这组指令(或这些步骤)时，都从变量的原值推出它的一个新值。最终得到问题的结果。

迭代算法适用于那些每步输入参数变量一定，前值可以作为下一步输入参数的问题。

典型例子比如说，用迭代算法计算斐波那契数列。

四、枚举算法

枚举算法是我们在日常中使用到的最多的一个算法，它的核心思想就是:枚举所有的可能。枚举法的本质就是从所有候选答案中去搜索正确地解。

枚举算法适用于候选答案数量一定的情况。

典型例子包括鸡钱问题，有公鸡5，母鸡3，三小鸡1，求m钱n鸡的所有可能解。可以采用一个三重循环将所有情况枚举出来。代码如下：

五、回溯算法

回溯算法是一个类似枚举的搜索尝试过程，主要是在搜索尝试过程中寻找问题的解，当发现已不满足求解条件时，就“回溯”返回，尝试别的路径。

许多复杂的，规模较大的问题都可以使用回溯法，有“通用解题方法”的美称。

典型例子是8皇后算法。在8 8格的国际象棋上摆放八个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问一共有多少种摆法。

回溯法是求解皇后问题最经典的方法。算法的思想在于如果一个皇后选定了位置，那么下一个皇后的位置便被限制住了，下一个皇后需要一直找直到找到安全位置，如果没有找到，那么便要回溯到上一个皇后，那么上一个皇后的位置就要改变，这样一直递归直到所有的情况都被举出。

六、动态规划算法

动态规划过程是：每次决策依赖于当前状态，又随即引起状态的转移。一个决策序列就是在变化的状态中产生出来的，所以，这种多阶段最优化决策解决问题的过程就称为动态规划。

动态规划算法适用于当某阶段状态给定以后，在这阶段以后的过程的发展不受这段以前各段状态的影响，即无后效性的问题。

典型例子比如说背包问题，给定背包容量及物品重量和价值，要求背包装的物品价值最大。

㈤ 算法怎么学

贪心算法的定义：

贪心算法是指在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，只做出在某种意义上的局部最优解。贪心算法不是对所有问题都能得到整体最优解，关键是贪心策略的选择，选择的贪心策略必须具备无后效性，即某个状态以前的过程不会影响以后的状态，只与当前状态有关。

解题的一般步骤是：

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

2.把求解的问题分成若干个子问题；

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

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

如果大家比较了解动态规划，就会发现它们之间的相似之处。最优解问题大部分都可以拆分成一个个的子问题，把解空间的遍历视作对子问题树的遍历，则以某种形式对树整个的遍历一遍就可以求出最优解，大部分情况下这是不可行的。贪心算法和动态规划本质上是对子问题树的一种修剪，两种算法要求问题都具有的一个性质就是子问题最优性(组成最优解的每一个子问题的解，对于这个子问题本身肯定也是最优的)。动态规划方法代表了这一类问题的一般解法，我们自底向上构造子问题的解，对每一个子树的根，求出下面每一个叶子的值，并且以其中的最优值作为自身的值，其它的值舍弃。而贪心算法是动态规划方法的一个特例，可以证明每一个子树的根的值不取决于下面叶子的值，而只取决于当前问题的状况。换句话说，不需要知道一个节点所有子树的情况，就可以求出这个节点的值。由于贪心算法的这个特性，它对解空间树的遍历不需要自底向上，而只需要自根开始，选择最优的路，一直走到底就可以了。

话不多说，我们来看几个具体的例子慢慢理解它：

1.活动选择问题

这是《算法导论》上的例子，也是一个非常经典的问题。有n个需要在同一天使用同一个教室的活动a1,a2,…,an，教室同一时刻只能由一个活动使用。每个活动ai都有一个开始时间si和结束时间fi 。一旦被选择后，活动ai就占据半开时间区间[si,fi)。如果[si,fi]和[sj,fj]互不重叠，ai和aj两个活动就可以被安排在这一天。该问题就是要安排这些活动使得尽量多的活动能不冲突的举行。例如下图所示的活动集合S，其中各项活动按照结束时间单调递增排序。

关于贪心算法的基础知识就简要介绍到这里，希望能作为大家继续深入学习的基础。