❶ 五大常用算法之一：贪心算法
所谓贪心选择性质是指所求问题的整体最优解可以通过一系列局部最优的选择，换句话说，当考虑做何种选择的时候，我们只考虑对当前问题最佳的选择而不考虑子问题的结果。这是贪心算法可行的第一个基本要素。贪心算法以迭代的方式作出相继的贪心选择，每作一次贪心选择就将所求问题简化为规模更小的子问题。 对于一个具体问题，要确定它是否具有贪心选择性质，必须证明每一步所作的贪心选择最终导致问题的整体最优解。
当一个问题的最优解包含其子问题的最优解时，称此问题具有最优子结构性质。问题的最优子结构性质是该问题可用贪心算法求解的关键特征。
值得注意的是，贪心算法并不是完全不可以使用，贪心策略一旦经过证明成立后，它就是一种高效的算法。比如， 求最小生成树的Prim算法和Kruskal算法都是漂亮的贪心算法 。
贪心算法还是很常见的算法之一，这是由于它简单易行，构造贪心策略不是很困难。
可惜的是，它需要证明后才能真正运用到题目的算法中。
一般来说，贪心算法的证明围绕着：整个问题的最优解一定由在贪心策略中存在的子问题的最优解得来的。
对于例题中的3种贪心策略，都是无法成立（无法被证明）的，解释如下：
贪心策略：选取价值最大者。反例：
W=30
物品：A B C
重量：28 12 12
价值：30 20 20
根据策略，首先选取物品A，接下来就无法再选取了，可是，选取B、C则更好。
（2）贪心策略：选取重量最小。它的反例与第一种策略的反例差不多。
（3）贪心策略：选取单位重量价值最大的物品。反例：
W=30
物品：A B C
重量：28 20 10
价值：28 20 10
根据策略，三种物品单位重量价值一样，程序无法依据现有策略作出判断，如果选择A，则答案错误。但是果在条件中加一句当遇见单位价值相同的时候,优先装重量小的,这样的问题就可以解决.
所以需要说明的是，贪心算法可以与随机化算法一起使用，具体的例子就不再多举了。（因为这一类算法普及性不高，而且技术含量是非常高的，需要通过一些反例确定随机的对象是什么，随机程度如何，但也是不能保证完全正确，只能是极大的几率正确）。
❷ 贪心算法的证明方法
贪心算法的基本思路如下：
1.建立数学模型来描述问题。
2.把求解的问题分成若干个子问题。
3.对每一子问题求解，得到子问题的局部最优解。
4.把子问题的解局部最优解合成原来解问题的一个解。
----------------------------------------------
其实归纳起来也就一个类。其他的都是分支
❸ 如何证明贪心算法
贪心算法的基本思路如下：
1.建立数学模型来描述问题。
2.把求解的问题分成若干个子问题。
3.对每一子问题求解，得到子问题的局部最优解。
4.把子问题的解局部最优解合成原来解问题的一个解。
❹ 关于编程的贪心法
定义
所谓贪心算法（又称贪婪算法）是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的仅是在某种意义上的局部最优解。 贪心算法不是对所有问题都能得到整体最优解，但对范围相当广泛的许多问题他能产生整体最优解或者是整体最优解的近似解。
[编辑本段]贪心算法的基本思路
1.建立数学模型来描述问题。 2.把求解的问题分成若干个子问题。 3.对每一子问题求解，得到子问题的局部最优解。 4.把子问题的解局部最优解合成原来解问题的一个解。 实现该算法的过程： 从问题的某一初始解出发； while 能朝给定总目标前进一步 do 求出可行解的一个解元素； 由所有解元素组合成问题的一个可行解。 下面是一个可以试用贪心算法解的题目，贪心解的确不错，可惜不是最优解。
[编辑本段]例题分析
[背包问题]有一个背包，背包容量是M=150。有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=150) （1）根据贪心的策略，每次挑选价值最大的物品装入背包，得到的结果是否最优？ （2）每次挑选所占重量最小的物品装入是否能得到最优解？ （3）每次选取单位重量价值最大的物品，成为解本题的策略。 值得注意的是，贪心算法并不是完全不可以使用，贪心策略一旦经过证明成立后，它就是一种高效的算法。 贪心算法还是很常见的算法之一，这是由于它简单易行，构造贪心策略不是很困难。 可惜的是，它需要证明后才能真正运用到题目的算法中。 一般来说，贪心算法的证明围绕着：整个问题的最优解一定由在贪心策略中存在的子问题的最优解得来的。 对于例题中的3种贪心策略，都是无法成立（无法被证明）的，解释如下： （1）贪心策略：选取价值最大者。 反例： W=30 物品：A B C 重量：28 12 12 价值：30 20 20 根据策略，首先选取物品A，接下来就无法再选取了，可是，选取B、C则更好。 （2）贪心策略：选取重量最小。它的反例与第一种策略的反例差不多。 （3）贪心策略：选取单位重量价值最大的物品。 反例： W=30 物品：A B C 重量：28 20 10 价值：28 20 10 根据策略，三种物品单位重量价值一样，程序无法依据现有策略作出判断，如果选择A，则答案错误。 【注意：如果物品可以分割为任意大小，那么策略3可得最优解】 对于选取单位重量价值最大的物品这个策略，可以再加一条优化的规则：对于单位重量价值一样的，则优先选择重量小的！这样，上面的反例就解决了。 但是，如果题目是如下所示，这个策略就也不行了。 W=40 物品：A B C 重量：28 20 15 价值：28 20 15 附：本题是个NP问题，用贪心法并不一定可以求得最优解，以后了解了动态规划算法后本题就有了新的解法。
[编辑本段]备注
贪心算法当然也有正确的时候。求最小生成树的Prim算法和Kruskal算法都是漂亮的贪心算法。 所以需要说明的是，贪心算法可以与随机化算法一起使用，具体的例子就不再多举了。（因为这一类算法普及性不高，而且技术含量是非常高的，需要通过一些反例确定随机的对象是什么，随机程度如何，但也是不能保证完全正确，只能是极大的几率正确）
[编辑本段]附贪心算法成功案例之一
马踏棋盘的贪心算法 123041-23 XX 【问题描述】 马的遍历问题。在8×8方格的棋盘上，从任意指定方格出发，为马寻找一条走遍棋盘每一格并且只经过一次的一条最短路径。 【初步设计】 首先这是一个搜索问题，运用深度优先搜索进行求解。算法如下： 1、 输入初始位置坐标x,y； 2、 步骤 c: 如果c> 64输出一个解，返回上一步骤c-- (x,y) ← c 计算(x,y)的八个方位的子结点，选出那此可行的子结点 循环遍历所有可行子结点，步骤c++重复2 显然（2）是一个递归调用的过程，大致如下： void dfs(int x,int y,int count) { int i,tx,ty; if(count> N*N) { output_solution();//输入一个解 return; }
❺ Leetcode 中 Jump Game II 为什么用贪心算法是对的，如何证明
如果你说的贪心是指
Jump Game II (最小步数到达终点，贪心) 【leetcode】
定义F(i,j)表示i步能否到达j，由题目性质知若F(i,j)=true则必有F(i,j-1)=true。
因此可以定义G(i)表示i步最远能到的格子，又由题目性质知G(i-1)<G(i)。
因此答案是minimum on i such that G(i) = n。
再由题目性质，G(i) = max(x+A(x) | 1<=x<=G(i-1))
所以是对的。
一般的，没有办法证明贪心算法是对的。
你看上面那么多“由题目性质”就知道了，不同的贪心算法的证明方法千奇百怪，充斥奇技淫巧，一般来说其证明远比算法本身难，具体参考《算法导论》。
❻ 漫谈算法如何证明贪心算法是最优 using exchange argument
这里主要是介绍一种证明贪心算法是最优的一种方法：Exchange Argument （不知道应该怎么翻译到中文，交换参数？感觉听起来挺别扭的，不像是一个方法的名字~o( □ )o）
Exchange Argument的主要的思想也就是 先假设 存在一个最优的算法和我们的贪心算法最接近，然后通过交换两个算法里的一个步骤(或元素)，得到一个新的最优的算法，同时这个算法比前一个最优算法更接近于我们的贪心算法，从而得到矛盾，原命题成立。
下面来看一个更为formal的解释：
步骤：
Step0: 给出贪心算法A的描述
Step1: 假设O是和A最相似(假设O和A的前k个步骤都相同，第k+1个开始不同，通常这个临界的元素最重要)的最优算法
Step2: [Key] 修改算法O(用Exchange Argument，交换A和O中的一个元素)，得到新的算法O’
Step3: 证明O’ 是feasible的，也就是O’是对的
Step4: 证明O’至少和O一样，即O’也是最优的
Step5: 得到矛盾，因为O’ 比O 更和A 相似。
证毕。
当然上面的步骤还有一个变种，如下：
Step0: 给出贪心算法A的描述
Step1: 假设O是一个最优算法（随便选，arbitrary）
Step2: 找出O和A中的一个不同。（当然这里面的不同可以是一个元素在O不再A，或者是一个pair的顺序在A的和在O的不一样。这个要根据具体题目）
Step3：Exchange这个不同的东西，然后argue现在得到的算法O 不必O差。
Step4: Argue 这样的不同一共有Polynomial个，然后我exchange Polynomial次就可以消除所有的不同，同时保证了算法的质量不比O差。这也就是说A 是as good as 一个O的。因为O是arbitrary选的，所以A是optimal的。
证毕
下面给几个例子：
例 Maximum Cardinality Disjoint Interval Problem
问题描述：给一些时间片段集合T={（a1，b1）（a2，b2），。。。，（an，bn）}，找出一个元素个数最多的子集S，子集中的每个元素的时间片段没有交叉。
Greedy Algorithm: 每次都选所有interval 中bi最小的那个，把（ai，bi）加入S，然后把（ai，bi）在T中删除，同时把T中所有和（ai，bi）有交叉的interval删除，然后再在T中找最小的bj，循环上面的操作，直到没有可以在添加的。
证明上面说的Greedy Algorithm是最优的。
下面就用第一个证明的步骤来证。
我们的Greedy Algorithm记为A，假设A不是最优的，那么就一定存在一个O，O是和A最相近的一个最优的算法，最相近是指和O和A的前K-1个选择都相同，第K个是不同的。
假设对于A，A第k个选择的是（ai，bi）；而O第K个选择的是（aj，bj）。从A的定义我们可以直到，bi<=bj。
❼ 贪心算法的本质
1. 贪心法（Greedy Algorithm）定义
求解最优化问题的算法通常需要经过一系列的步骤，在每个步骤都面临多种选择；
贪心法就是这样的算法：它在每个决策点作出在当时看来最佳的选择，即总是遵循某种规则，做出局部最优的选择，以推导出全局最优解（局部最优解->全局最优解）
2. 对贪心法的深入理解
（1）原理：一种启发式策略，在每个决策点作出在当时看来最佳的选择
（2）求解最优化问题的两个关键要素：贪心选择性质+最优子结构
①贪心选择性质：进行选择时，直接做出在当前问题中看来最优的选择，而不必考虑子问题的解；
②最优子结构：如果一个问题的最优解包含其子问题的最优解，则称此问题具有最优子结构性质
（3）解题关键：贪心策略的选择
贪心算法不是对所有问题都能得到整体最优解的，因此选择的贪心策略必须具备无后效性，即某个状态以前的过程不会影响以后的状态，只与当前状态有关。
（4）一般步骤：
①建立数学模型来描述最优化问题；
②把求解的最优化问题转化为这样的形式：对其做出一次选择后，只剩下一个子问题需要求解；
③证明做出贪心选择后：
1°原问题总是存在全局最优解，即贪心选择始终安全；
2°剩余子问题的局部最优解与贪心选择组合，即可得到原问题的全局最优解。
并完成2°
3. 贪心法与动态规划
最优解问题大部分都可以拆分成一个个的子问题，把解空间的遍历视作对子问题树的遍历，则以某种形式对树整个的遍历一遍就可以求出最优解，大部分情况下这是不可行的。贪心算法和动态规划本质上是对子问题树的一种修剪，两种算法要求问题都具有的一个性质就是子问题最优性(组成最优解的每一个子问题的解，对于这个子问题本身肯定也是最优的)。动态规划方法代表了这一类问题的一般解法，我们自底向上构造子问题的解，对每一个子树的根，求出下面每一个叶子的值，并且以其中的最优值作为自身的值，其它的值舍弃。而贪心算法是动态规划方法的一个特例，可以证明每一个子树的根的值不取决于下面叶子的值，而只取决于当前问题的状况。换句话说，不需要知道一个节点所有子树的情况，就可以求出这个节点的值。由于贪心算法的这个特性，它对解空间树的遍历不需要自底向上，而只需要自根开始，选择最优的路，一直走到底就可以了。
❽ 贪心算法中，通常会让证明贪心选择性，请问，证明贪心选择性的实质是什么怎样说明一个问题具有贪心选择呢
一般都是要最省事的比如
设有n中不同面值的硬币，个硬币的面值春雨数组T[1：n]中，现在要用这些面值的硬币来找钱。可以使用的各种面值的硬币个数存于数组Coins[1:n]中。
对任意签署0<=m<=20001，设计一个用最少硬币找钱m的方法。
用贪心算法，先用最大面值的，直到超出之前再改用更小面值的，超出之前再用更更小面值的。。直到正好。这样最少
程序实例
#include<stdio.h>
void main()
{
int m;
int i;
printf("please input m:");
scanf("%d",&m);
int T[6] ={100,50,20,10,5,1};
int coins[6] = {0};
for(i = 0; i < 6; )
{
if(m < T[i])
{
i++;
continue;
}
while(m >= T[i])
{
m -= T[i];
coins[i]++;
}
i++;
}
for(i = 0; i < 6; i++)
if(coins==0)
printf("%-4d有 %-2d张\n",T[i],coins[i]);
printf("\n");
}
❾ 贪心算法的证明过程，是不是只有先证明了贪心选择性质之后，再以贪心选择为前提证明其最优子结构
对于一个具体问题，要确定它是否具有贪心选择性质，必须证明每一步所作的贪心选择最终导致问题的整体最优解。
证明的大致过程为：首先考察问题的一个整体最优解，并证明可修改这个最优解，使其以贪心选择开始。做了贪心选择后，原问题简化为规模更小的类似子问题。然后用数学归纳法证明通过每一步做贪心选择，最终可得到问题的整体最优解。其中，证明贪心选择后的问题简化为规模更小的类似子问题的关键在于利用该问题的最优子结构性质。
❿ [算法] 贪心算法证明思路
动态规划和贪心算法都需要问题具有最优子结构，但不同的是贪心 自顶向下 ，先做选择再求解一个结果子问题，而动态规划自底向上求解子问题，需要先求出子问题的最优解再做选择。这是因为，动态规划最优解有两个子问题时，求解子问题 时有j-i-1种选择，但贪心选择特征能够使 其中一个子问题必定为空 ，这种子问题和选择数目的减少使得子问题能够自顶向下被解决。
a) 定义子问题空间，做出一个选择从而产生一个或多个子问题。子问题空间的定义结合需要求解的目标和选择后子问题的描述刻画来考虑。
b) 利用“剪切-粘贴”证明作为最优解的组成部分的每个子问题的解也是它本身的最优解。如果子问题的解不是最优解，将其替换为对应的最优解从而一定能得到原问题一个更优的解，这与最初的解是原问题的最优解的前提假设矛盾，因此最优子结构得证。
贪心的本质是局部最优解能产生全局最优解，即产生两个子问题 和 时，可以直接解决子问题 （在子问题 中，使用贪心策略选择a作为局部最优解）然后对子问题 进行分解，最终可以合并为全局最优解。
因此，要证明贪心选择性质只需要证明 存在一个最优解是通过当前贪心选择策略得到的 ，反过来，即证明**通过非贪心策略得到的原问题的最优解中也一定包含局部最优解a。
定义通过非贪心策略的选择可以得到的一个最优解A，将最优解中的元素和当前贪心策略会选择的元素逐个交换后得到的解A'并不比
A差（假设贪心策略会选择的元素在当前最优解中未被选择，通过“剪切-粘贴”证明得到的仍是最优解），可以证明存在原问题的最优解可以通过贪心选择得到。