哪些算法是贪心算法,属于贪心算法的是

　　贪婪算法详解文章目录什么是贪婪算法？贪婪算法适用条件详解？极度贪婪/各个击破/dp在总结算法上的区别？例题改题？股票问题？糖果背包分配问题？0-1背包问题？背包问题的一部分

　　020.03.04增加指示灯代码-45-跳游戏二

　　020.03.05添加指示灯代码-435-无重复零件

　　020.03.10删除和添加指示灯代码-402位数字

　　参考：

　　贪婪算法细节

　　程序员算法基础——贪婪算法

　　详细求解贪婪算法(Python实现贪婪算法的典型例子))

　　递归、分治算法、动态规划和贪婪选择的区别

　　贪婪算法是狭义的。

贪心算法

　　广义贪婪是指基于当前情况做出贪婪决策的一种常见贪婪策略。

　　适用条件符合贪婪策略。

　　贪婪选择的本质是指可以通过一系列局部最优选择来达到所需问题的整体最优解，即贪婪选择。这是贪婪算法可行的第一个基本要素，也是贪婪算法与动态规划算法的主要区别。

　　贪婪算法通常以自上而下的方式进行，贪婪的选择以迭代的方式一个接一个地进行。每当做出贪婪的选择时，要解决的问题就变成了一个更小规模的子问题。

　　判断一个具体问题是否具有贪婪选择的性质，必须证明每一步做出的贪婪选择最终会导致问题的整体最优解。

　　最优子结构的性质

　　据说，如果一个问题的最优解包含子问题的最优解，则该问题具有最优子结构的性质。问题的最优子结构性质是问题可以用动态规划算法或贪婪算法求解的一个重要特征。

　　总结如下。

　　选择的本质(指在解决一个问题的过程中，每个阶段的选择都是当前状态下的最优选择，即局部最优选择。只要最终能得到问题的整体最优解，这个问题就可以通过贪婪选择来解决。在这种情况下，这个问题具有贪婪选择的性质。

　　最优子结构的性质：如果一个问题的最优解包含其子问题的最优解，则该问题有最优子结构。

　　算法的实现过程：

　　从问题的初始解决方案开始

　　同时可以朝着既定的总体目标进一步努力。

　　求可行解的一个解元素；

　　构造所有组合解元问题的可行解

　　总结算法的局限性是逐渐逼近有问题的初始解给定的目标，尽快得到更好的解。当到达算法的某个步骤时，算法停止，并且不能再执行。

　　这个算法有问题：

　　不能保证得到的最终解是最好的；

　　找不到最大或最小解；

　　只能找到满足某个约束的可行解的范围。

　　贪婪/分治/dp差异

　　贪婪算法：贪婪算法采用逐步构造最优解的方法。在每个阶段，根据一定的标准做出最合适的决定。一旦决定了，就不能改变。做出这种局部最优决策的准则称为贪婪准则。

　　分而治之算法：分而治之的思想是把一个很难直接解决的大问题分成容易解决的子问题，分别进行分而治之。

　　动态规划：把要解决的问题分解成几个子问题，依次解决子问题。正面问题的解决方案提供了有助于解决背面问题的信息。当解决任何局部问题时，列出所有可能的局部解决方案，留下具有最佳可能决策的局部解决方案，丢弃其他局部解决方案。依次求解每个子问题，最后一个子问题就是初始问题的解。

　　请参考：

　　递归、分治算法、动态规划和贪婪选择的区别

　　考试

　　想法：贪婪攻略优先选择大面额的纸币，然后设置延迟。

　　constgivechange=(money，count，k ) )={ let map=new Map、sum=0、i=0、RES=0；for(letI=0；imoney.lengthI ) ) map.set(money[I]，count[I]；sum=money[I]* count[I]；//当店员持有的零钱金额完全不足零钱所需的钱时if(sumk)返回nullMoney.sort((a，b)=b-a)；而(imoney。length)if)k=money[I])letn=math . floor)k/money[I]；

　　//如果只使用最大面额If(n=map . get(money[I]){ n=map . get(money[I])；} k-=n * money[I]；RES=n；console . info(` use $ { n } $ { money[I]} `)；}我；} return res};问题121。买卖股票的最佳时机。

　　12.买卖股票的最佳时机2

　　源代码：github

　　分发糖果参考：[leetcode]贪婪算法——分发糖果(135)

　　35.分发糖果。

　　解决这个问题的办法很巧妙，github。

　　背包问题0-1背包问题显而易见，我们在详细讲解回溯法的文章中已经说过，背包问题可以用回溯算法来解决。但是研究了这个贪婪算法之后，我们可以发现回溯算法只解决了0-1背包问题，下面会详细介绍。

　　所谓0-1背包问题，就是只有一个备用物品，我们只有选择和不选择两种情况。

　　如上所述，我们可以用回溯法来解决0-1背包问题，但是经过比较，我们会发现如果用迭代或者dp来解决，思路更清晰。

　　参考资料：

　　彻底理解0-1背包问题

　　/** * @param w权重项数组* @param v值项数组* @param idx当前待选项索引* @param capacity当前背包有效容量* @ returns { number } *//为什么要写状态转移方程？有国家吗？第一，如果最优答案中没有X项，那么此时的组合可能就是c-w[x]的最大值。//因此，我们发现当前状态可能与之前的状态有关。//首先确定状态转移方程：F (I，n)=Max (F (I-1，n)，V (I) F (I-1，n)//不要放idx项的总值let RES=backpackage(w，V，idx-1，capacity)；if(w[idx]=capacity){ RES=math . max(RES，v[idx]backpackage(w，v，idx-1，capacity-w[idx])；} return res};/** *优化背包问题0-1存储已获结果* @ paramw * @ paramv * @ paramc * @ returns { number } */constnapsack 1=(w，v，c)={ let memo=new array(w . length)；for(设I=0；imemo.lengthI){ memo[I]=新数组(C1)；} const solveKS=(w，v，idx，C)={ if(idx0C=0)返回0；if(memo[idx][C])返回memo[idx][C]；设res=solveKS(w，v，idx-1，C)；if(w[idx]C){ res=Math.max(res，v[idx] solveKS(w，v，idx-1，C-w[idx])；} memo[idx][C]=RES；返回res};返回solveKS(w，v，w.length-1，C)；};/* * *求解0-1背包问题的动态规划算法* @ param w * @ param v * @ param c */constnapsack 2=(w，v，c)={ let size=w . length；if(size===0)返回0；//这个矩阵的意义是dp[i][j]代表容量为J的背包中前I ^ 1个物品的最大值，设DP=new Array(size)；for(设I=0；isizeI){ DP[I]=新数组(C 1)；}//为什么要初始化第一行？因为容量为J//的背包只放一件物品时的值是边界值//初始化第一行，只考虑容量为C的背包放第0件物品的情况for(设I=0；iC 1；i ){ dp[0][i]=w[0]=i？v[0]:0；}//填充其他行for(设I=1；isizei ){ for(设j=0；jc1；J ){ //首先，设定值是放入第I项时的值DP[I][j]=DP[I-1][j]；If(w[i]=j){ //关键：这一步保证了总重量不会超过背包的容量，背包的容量为j dp [i] [j]=math.max (dp [i] [j]，v [i] dp [i-1] [j-w [i]。} } }控制台. info(DP)；返回DP[size-1][C]；};部分背包问题参考文献：

　　贪婪算法-部分背包问题

　　Java实现了一些背包问题。

　　一些背包问题的求解，很类似于变的套路。零钱的贪心目的是用最少的张数表示最大的面额，而一些背包问题可以用最大值而不超重。所以我们的贪心策略就是永远选择性价比高的，然后再推回去。//有些背包问题的解法很类似于变化的套路。零钱贪婪的目的是用最少的张数表示最大的面额。//但是，有些背包问题可以在不超重的情况下使用最大值。所以我们的贪心策略就是永远选择性价比高的，然后再推回去。/* *按性价比排序* @ param w * @ param v */constsort=(w，v)={ let temp=[]；for(设I=0；iw .长度；i ){ temp[i]=w[i]===0？0:v[I]/w[I]；} for(设I=temp . length-1；I=0；i - ){ for(设j=0；j=I；j){ if(temp[j]temp[j 1]){ let temp 0=temp[j]；temp[j]=temp[j 1]；temp[j 1]=temp 0；设temp 1=v[j]；v[j]=v[j 1]；v[j 1]=temp 1；设temp 2=w[j]；w[j]=w[j 1]；w[j 1]=temp 2；} } }};const knapsackPart=(w，v，c)={ let res=0，left=c，cn=new Map()；sort(w，v)；for(设I=0；四.长度；I){ if(left=0)break；设temp 0=left/w[I]；if (temp0=1) { cn.set(w[i]，temp 0)；left=left-temp 0 * w[I]；RES=temp 0 * v[I]；} else { cn.set(w[i]，1)；left-=w[I]；RES=v[I]；} } console . info(cn)；返回res};Jump Game ii-leetcode-45这是贪婪算法的典型应用，当然也是基于题目要求：我们总能到达最后一个位置，所以总能跳得很远。

　　const jump=nums={ let end=0，maxPosition=0，steps=0；for(设I=0；inums . length-1；I ){ //总能找到最大位置max position=math . max(max position，nums[I]I)；console.info(maxP==，max position)；if(I===end){ end=max position；步骤；} }返回步骤；};非重叠区间-leetcode-435 //非重叠区间-leetcode-435//给定一组区间，求要去掉的最小区间数，使其余区间不互相重叠。//注意：//可以认为区间的结束总是大于它的开始。//区间[1，2]和[2，3]的边界互相“接触”，但不互相重叠。//输入：[[1，2]，[2，3]，[3，4]，[1，3] ]//输出：1//说明：去掉[1，3]后，剩下的区间不重叠。一般拿到这个题目后想到的第一个方法就是根据起点或者终点对数组中的元素进行排序。题目要求的是找到需要去掉的元素的最少个数。====从这个问题开始，我们其实可以反过来考虑，最多几个元素就可以形成一个大区间，相互不重叠。我个人觉得这是一种很辛苦的思维方式，很值得思考。

　　参考我的github代码。

　　删除k位数字-leetcode-402给定一个由字符串表示的非负整数num，从该数中删除k位数字，以最小化剩余的数字。

　　在解决这个问题的过程中，会用到栈和贪婪算法的结合，同时也需要一些数学知识来解决这个问题。显然是一个需要很强的总结规律能力的问题。

　　详情请参考我的github。