贪心算法分析

① 贪心算法的例题分析

例题1、
[0-1背包问题]有一个背包，背包容量是M=150。有7个物品，物品不可以分割成任意大小。
要求尽可能让装入背包中的物品总价值最大，但不能超过总容量。
物品 A B C D E F G
重量 35kg 30kg 6kg 50kg 40kg 10kg 25kg
价值 10$ 40$ 30$ 50$ 35$ 40$ 30$
分析：
目标函数：∑pi最大
约束条件是装入的物品总重量不超过背包容量：∑wi<=M(M=150）
⑴根据贪心的策略，每次挑选价值最大的物品装入背包，得到的结果是否最优？
⑵每次挑选所占重量最小的物品装入是否能得到最优解？
⑶每次选取单位重量价值最大的物品，成为解本题的策略。
值得注意的是，贪心算法并不是完全不可以使用，贪心策略一旦经过证明成立后，它就是一种高效的算法。
贪心算法还是很常见的算法之一，这是由于它简单易行，构造贪心策略不是很困难。
可惜的是，它需要证明后才能真正运用到题目的算法中。
一般来说，贪心算法的证明围绕着：整个问题的最优解一定由在贪心策略中存在的子问题的最优解得来的。
对于例题中的3种贪心策略，都是无法成立（无法被证明）的，解释如下：
⑴贪心策略：选取价值最大者。
反例：
W=30
物品：A B C
重量：28 12 12
价值：30 20 20
根据策略，首先选取物品A，接下来就无法再选取了，可是，选取B、C则更好。
⑵贪心策略：选取重量最小。它的反例与第一种策略的反例差不多。
⑶贪心策略：选取单位重量价值最大的物品。
反例：
W=30
物品：A B C
重量：28 20 10
价值：28 20 10
根据策略，三种物品单位重量价值一样，程序无法依据现有策略作出判断，如果选择A，则答案错误。
【注意：如果物品可以分割为任意大小，那么策略3可得最优解】
对于选取单位重量价值最大的物品这个策略，可以再加一条优化的规则：对于单位重量价值一样的，则优先选择重量小的！这样，上面的反例就解决了。
但是，如果题目是如下所示，这个策略就也不行了。
W=40
物品：A B C
重量：25 20 15
价值：25 20 15
附：本题是个DP问题，用贪心法并不一定可以求得最优解，以后了解了动态规划算法后本题就有了新的解法。
例题2、
马踏棋盘的贪心算法
123041-23 XX
【问题描述】
马的遍历问题。在8×8方格的棋盘上，从任意指定方格出发，为马寻找一条走遍棋盘每一格并且只经过一次的一条路径。
【初步设计】
首先这是一个搜索问题，运用深度优先搜索进行求解。算法如下：
⒈ 输入初始位置坐标x,y；
⒉ 步骤 c:
如果c> 64输出一个解，返回上一步骤c--
（x,y) ← c
计算(x,y）的八个方位的子结点，选出那些可行的子结点
循环遍历所有可行子结点，步骤c++重复2
显然⑵是一个递归调用的过程，大致如下：
C++程序： #defineN8voiddfs(intx,inty,intcount){inti,tx,ty;if(count>N*N){output_solution();//输出一个解return;}for(i=0;i<8;i++){tx=hn[i].x;//hn[]保存八个方位子结点ty=hn[i].y;s[tx][ty]=count;dfs(tx,ty,count+1);//递归调用s[tx][ty]=0;}}Pascal程序： ProgramYS;ConstFXx:array[1..8]of-2..2=（1,2,2,1,-1,-2,-2,-1）；FXy:array[1..8]of-2..2=（2,1,-1,-2,-2,-1,1,2）；VarRoad:array[1..10,1..10]ofinteger;x,y,x1,y1,total:integer;ProcereFind(x,y:integer);varNx,Ny,i:integer;BeginFori:=1to8dobegin{8个方向}If(x+FXx[i]in[1..8])and(y+FXy[i]in[1..8])Then{确定新坐标是否越界}IfRoad[x+Fxx[i],y+Fxy[i]]=0Thenbegin{判断是否走过}Nx:=x+FXx[i];Ny:=y+FXy[i];Road[Nx,Ny]:=1;{建立新坐标}If(Nx=x1）and(Ny=y1）Theninc(total)elseFind(Nx,Ny);{递归}Road[Nx,Ny]:=0{回朔}endendEnd;BEGIN{Main}Total:=0;FillChar(Road,sizeof(road),0);Readln(x,y);{读入开始坐标}Readln(x1,y1）；{读入结束坐标}If(x>10）or(y>10）or(x1>10）or(y1>10）Thenwriteln('Error'){判断是否越界}ElseFind(x,y);Writeln('Total:',total){打出总数}END.这样做是完全可行的，它输入的是全部解，但是马遍历当8×8时解是非常之多的，用天文数字形容也不为过，这样一来求解的过程就非常慢，并且出一个解也非常慢。
怎么才能快速地得到部分解呢？
【贪心算法】
其实马踏棋盘的问题很早就有人提出，且早在1823年，J.C.Warnsdorff就提出了一个有名的算法。在每个结点对其子结点进行选取时，优先选择‘出口’最小的进行搜索，‘出口’的意思是在这些子结点中它们的可行子结点的个数，也就是‘孙子’结点越少的越优先跳，为什么要这样选取，这是一种局部调整最优的做法，如果优先选择出口多的子结点，那出口少的子结点就会越来越多，很可能出现‘死’结点（顾名思义就是没有出口又没有跳过的结点），这样对下面的搜索纯粹是徒劳，这样会浪费很多无用的时间，反过来如果每次都优先选择出口少的结点跳，那出口少的结点就会越来越少，这样跳成功的机会就更大一些。这种算法称为为贪心算法，也叫贪婪算法或启发式算法，它对整个求解过程的局部做最优调整，它只适用于求较优解或者部分解，而不能求最优解。这样的调整方法叫贪心策略，至于什么问题需要什么样的贪心策略是不确定的，具体问题具体分析。实验可以证明马遍历问题在运用到了上面的贪心策略之后求解速率有非常明显的提高，如果只要求出一个解甚至不用回溯就可以完成，因为在这个算法提出的时候世界上还没有计算机，这种方法完全可以用手工求出解来，其效率可想而知。

② 算法分析与设计这门课程第四章贪心算法的知识点有哪些

算法分析与设计这门课第四章贪心算法的知识点包含章节导引,第一节活动安排问题,第二节贪心算法基本要素,第三节最优装载,第四节单源最短路径,第五节多机调度问题,课后练习,。

③ 贪心算法 部分背包问题

[背包问题]有一个背包，背包容量是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，则答案错误。

④ 找零钱问题的贪心算法

问题描述：
当前有面值分别为2角5分，1角，5分，1分的硬币，请给出找n分钱的最佳方案（要求找出的硬币数目最少）
问题分析：
根据常识，我们到店里买东西找钱时，老板总是先给我们最大面值的，要是不够再找面值小一点的，直到找满为止。如果老板都给你找分数的或者几角的，那你肯定不干，另外，他也可能没有那么多零碎的钱给你找。其实这就是一个典型的贪心选择问题。
问题的算法设计与实现：
先举个例子，假如老板要找给我99分钱，他有上面的面值分别为25，10，5，1的硬币数，为了找给我最少的硬币数，那么他是不是该这样找呢，先看看该找多少个25分的， 99／25＝3，好像是3个，要是4个的话，我们还得再给老板一个1分的，我不干，那么老板只能给我3个25分，由于还少给我24，所以还得给我2个10分的和4个1分。
具体实现
//找零钱算法
//By falcon
//输入：数组m，依次存放从大到小排列的面值数，n为需要找的钱数，单位全部为分
//输出：数组num，对照数组m中的面值存放不同面值的硬币的个数，即找钱方案

⑤ tsp问题的贪心算法，分析时间复杂度，试分析是否存在o的有效算法

贪心算法（又称贪婪算法）是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的仅是在某种意义上的局部最优解。贪心算法不是对所有问题都能得到整体最优解，但对范围相当广泛的许多问题他能产

⑥ 大学课程《算法分析与设计》中动态规划和贪心算法的区别和联系

《算法分析与设计》是一门理论与应用并重的专业课程。本课程以算法设计策略为知识单元，系统介绍计算机算法的设计方法和分析技巧。课程主要内容包括:第1章，算法概述；第二章，递归和分治策略；第三章，动态规划；第四章，贪婪算法；第五章，回溯法；第六章，分枝定界法。通过介绍经典实用的算法，使学生掌握算法设计的基本方法。结合案例分析，让学生深入了解算法设计的技巧和分析算法的能力。

⑦ 求一个算法(贪心算法)

贪心算法

一、算法思想

贪心法的基本思路：
——从问题的某一个初始解出发逐步逼近给定的目标，以尽可能快的地求得更好的解。当达到某算法中的某一步不能再继续前进时，算法停止。
该算法存在问题：
1. 不能保证求得的最后解是最佳的；
2. 不能用来求最大或最小解问题；
3. 只能求满足某些约束条件的可行解的范围。

实现该算法的过程：
从问题的某一初始解出发；
while 能朝给定总目标前进一步 do
求出可行解的一个解元素；
由所有解元素组合成问题的一个可行解；

二、例题分析

1、[背包问题]有一个背包，背包容量是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，则答案错误。

所以需要说明的是，贪心算法可以与随机化算法一起使用，具体的例子就不再多举了。（因为这一类算法普及性不高，而且技术含量是非常高的，需要通过一些反例确定随机的对象是什么，随机程度如何，但也是不能保证完全正确，只能是极大的几率正确）

================================
三个经典的贪心算法

有人说贪心算法是最简单的算法，原因很简单：你我其实都很贪，根本不用学。有人说贪心算法是最复杂的算法，原因也很简单：这世上贪的人太多了，那轮到你我的份？

不论难度如何，贪心算法都是一个很重要的算法，我在网上N多Online Judge中的题目中，总结了三类较为常见，也十分经典的贪心算法，发布在这儿Just For Fun。

（注：由于没有现成的名字可用，这三种类型贪心算法的名字都是我自己取的，如果你听着别扭，请见谅。）

No 1.线段覆盖（linescover）

题目大意：

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

解题思路：

将线段按其坐标进行排序（排序的具体方法:按起始坐标排，起始坐标相同的按终止坐标排，都是小在前大在后）,使之依次递增，并按顺序分别编号为X(i),X(i).a代表其起始坐标，X(i).b代表其终止坐标。

然后按排好的顺序依次处理：定义一个变量last记录考虑到当前线段之时被线段覆盖的最大的坐标值，再定义一个变量length记录当前线段覆盖的长度。对于后面的线段，我们把它看成由两个部分组成，即把它分成last之前的线段和last之后的线段。（如果线段全部处在last之后，其last之前的部分不存在。）由于我们排过序，我们可以肯定当前考虑的线段X(i)其处在last之前的部分不会对length造成影响（因为X(i-1).b=last，X(i).a>=X(i-1).a,即X(i)在last之前的部分所处位置肯定被线段X(i-1)覆盖过），所以会对length产生影响的即是X(i)处在last之后的部分。

所以我们可以依次对每条线段做如下处理：（初始化length为零，last为负无穷）

length+=X(i).b-last (X(i).a<=last 且 X(i).b>=last)

length+=X(i).b-X(i).a (X(i).a>last)

last=X(i).b;

最后length就为我们所需要的答案。

No 2.最优数对（bestpair）

题目大意：

按递增的顺序告诉你N个正整数和一个实数P，要求求出求出该数列中的比例最接近P的两个数（保证绝对没有两个数使得其比值为P）。

解题思路：

定义两个指针i和j，先初始化i=j=1，然后进行如下操作：

当code[j]/code[i]>p时，inc（j）；

当code[j]/code[i]<p时，inc（i）。

记录其中产生的最优值即为答案。

No 3.连续数之和最大值（maxsum）

题目大意：

给出一个长度为N的数列（数列中至少有一个正数），要求求出其中的连续数之和的最大值。（也可以加入a和b来限制连续数的长度不小于a且不大于b）。

解题思路：

先说不加限制的那种，定义一个统计变量tot，然后用循环进行如下操作：inc（tot，item） 其中如果出现tot<0的情况，则将tot赋值为0。在循环过程之中tot出现的最大值即为答案。

如果加入了限制条件的话，问题就变得难一些了（这句真的不是废话）。为此我们先定义数组sum[i]来表示code[1]到code[i]之和（这样的话code[a]~code[b]的和我们就可以用sum[b]-sum[a-1]来表示了。）。

再维护一个数组hash[i]来表示满足条件的sum[a-1]的下标，并使之按递增顺序排列，这样当前以第i的数为终止的数列的最大值肯定就是sum[i]-sum[hash[1]]。

现在我们来讨论hash数组之中的数据需要满足的条件和如何维护的具体问题：

当考虑到以第i个数为结尾时，hash[i]所表示的下标需要满足的第一个条件就是题目规定的长度限制，我们需要实时的加入满足长度规定的下标，删除不符合要求的下标。其次，与不加限制条件时相同，若sum[i]-sum[hash[1]]的值小于零，则清空数组hash。

维护时可以这样，当考虑到第i个数时，我们就将下标i-a+1加入到hash中，因为hash中原来已经排好序，因此我们我们可以用插入排序来维护hash的递增性，然后我们考察hash[1]，若hash[1]<i-b+1，则证明其已超出长度限制，我们就将其删除，接着再考虑更新后的hash[1],如此重复直至找到一个满足条件的hash[1]为止。

我们可以用链表来表示hash，这样就可以减少数据加入和删除时频繁数据移动的时间消耗。

记录下sum[i]-sum[hash[1]]的最大值即为答案。

⑧ 采用贪心算法进行安排。对算法的时间和空间复杂度进行分析

时间主要是 排序用时了，快速排序 一般是 o(n*logn)
空间 复杂度基本上是 0(1)

⑨ 什么是贪心算法，用实例分析贪心算法是如何解决实际问题

比如： int a=3,b=4,c; c=a+++b; 将被解释为 c=(a++)+b; 而不会被解释为 c=a+(++b); 贪心算法的主要意义是从左至右依次解释最多的符号！

⑩ 分析用动态规划和贪心算法求解背包问题的差异

动态规划本质是以空间换时间，算出了所有可行解的值域。

而贪心算法，每次选则最优的，而结果未必最优。
举个简单例子。
背包能装8kg,有3个物品，分别为3kg,4kg,5kg
动态规划，是计算，3+4， 3+5，得出解，最大的是3+5=8kg
贪心算法，是选择，第一次选最大的：5kg<8kg，第二次选则剩下的最大的4kg，4+5>8,故而解为5kg。