贪心算法详解分析.docx
《贪心算法详解分析.docx》由会员分享，可在线阅读，更多相关《贪心算法详解分析.docx（33页珍藏版）》请在冰点文库上搜索。
贪心算法详解分析
贪心算法详解
贪心算法思想：
顾名思义，贪心算法总是作出在当前看来最好的选择。
也就是说贪心算法并不从整体最优考虑，它所作出的选择只是在某种意义上的局部最优选择。
当然，希望贪心算法得到的最终结果也是整体最优的。
虽然贪心算法不能对所有问题都得到整体最优解，但对许多问题它能产生整体最优解。
如单源最短路经问题，最小生成树问题等。
在一些情况下，即使贪心算法不能得到整体最优解，其最终结果却是最优解的很好近似。
贪心算法的基本要素：
1.贪心选择性质。
所谓贪心选择性质是指所求问题的整体最优解可以通过一系列局部最优的选择，即贪心选择来达到。
这是贪心算法可行的第一个基本要素，也是贪心算法与动态规划算法的主要区别。
动态规划算法通常以自底向上的方式解各子问题，而贪心算法则通常以自顶向下的方式进行，以迭代的方式作出相继的贪心选择，每作一次贪心选择就将所求问题简化为规模更小的子问题。
对于一个具体问题，要确定它是否具有贪心选择性质，必须证明每一步所作的贪心选择最终导致问题的整体最优解。
2.当一个问题的最优解包含其子问题的最优解时，称此问题具有最优子结构性质。
问题的最优子结构性质是该问题可用动态规划算法或贪心算法求解的关键特征。
贪心算法的基本思路：
从问题的某一个初始解出发逐步逼近给定的目标，以尽可能快的地求得更好的解。
当达到算法中的某一步不能再继续前进时，算法停止。
该算法存在问题：
1.不能保证求得的最后解是最佳的；
2.不能用来求最大或最小解问题；
3.只能求满足某些约束条件的可行解的范围。
实现该算法的过程：
从问题的某一初始解出发；
while能朝给定总目标前进一步do
求出可行解的一个解元素；
由所有解元素组合成问题的一个可行解；
用背包问题来介绍贪心算法：
背包问题：
有一个背包，背包容量是M=150。
有7个物品，物品可以分割成任意大小。
要求尽可能让装入背包中的物品总价值最大，但不能超过总容量。
物品ABCDEFG
重量35306050401025
价值10403050354030
分析如下
目标函数：
∑pi最大
约束条件是装入的物品总重量不超过背包容量：
∑wi<=M（M=150）。
（1）根据贪心的策略，每次挑选价值最大的物品装入背包，得到的结果是否最优？
（2）每次挑选所占重量最小的物品装入是否能得到最优解？
（3）每次选取单位重量价值最大的物品，成为解本题的策略。
值得注意的是，贪心算法并不是完全不可以使用，贪心策略一旦经过证明成立后，它就是一种高效的算法。
贪心算法还是很常见的算法之一，这是由于它简单易行，构造贪心策略不是很困难。
可惜的是，它需要证明后才能真正运用到题目的算法中。
一般来说，贪心算法的证明围绕着：
整个问题的最优解一定由在贪心策略中存在的子问题的最优解得来的。
对于背包问题中的3种贪心策略，都是无法成立（无法被证明）的，解释如下：
贪心策略：
选取价值最大者。
反例：
W=30
物品：
ABC
重量：
281212
价值：
302020
根据策略，首先选取物品A，接下来就无法再选取了，可是，选取B、C则更好。
（2）贪心策略：
选取重量最小。
它的反例与第一种策略的反例差不多。
（3）贪心策略：
选取单位重量价值最大的物品。
反例：
W=30
物品：
ABC
重量：
282010
价值：
282010
根据策略，三种物品单位重量价值一样，程序无法依据现有策略作出判断，如果选择A，则答案错误。
但是果在条件中加一句当遇见单位价值相同的时候,优先装重量小的,这样的问题就可以解决.
所以需要说明的是，贪心算法可以与随机化算法一起使用，具体的例子就不再多举了。
（因为这一类算法普及性不高，而且技术含量是非常高的，需要通过一些反例确定随机的对象是什么，随机程度如何，但也是不能保证完全正确，只能是极大的几率正确）。
下面我们看一些简单例题。
例24：
在N行M列的正整数矩阵中，要求从每行中选出1个数，使得选出的总共N个数的和最大。
分析：
要使总和最大，则每个数要尽可能大，自然应该选每行中最大的那个数。
因此，我们设计出如下算法:
读入N,M,矩阵数据；
Total:
=0;
ForI:
=1toNdobegin{对N行进行选择}
选择第I行最大的数,记为K；
Total:
=Total+K；
End；
输出最大总和Total；
从上例中我们可以看出，和递推法相仿，贪心法也是从问题的某一个初始解出发，向给定的目标递推。
但不同的是，推进的每一步不是依据某一固定的递推式，而是做一个局部的最优选择，即贪心选择（在例中，这种贪心选择表现为选择一行中的最大整数），这样，不断的将问题归纳为若干相似的子问题，最终产生出一个全局最优解。
特别注意的是是，局部贪心的选择是否可以得出全局最优是能否采用贪心法的关键所在。
对于能否使用贪心策略，应从理论上予以证明。
下面我们看看另一个问题。
例25：
部分背包问题
给定一个最大载重量为M的卡车和N种食品，有食盐，白糖，大米等。
已知第i种食品的最多拥有Wi公斤，其商品价值为Vi元/公斤，编程确定一个装货方案，使得装入卡车中的所有物品总价值最大。
分析：
因为每一个物品都可以分割成单位块，单位块的利益越大显然总收益越大，所以它局部最优满足全局最优，可以用贪心法解答，方法如下：
先将单位块收益按从大到小进行排列，然后用循环从单位块收益最大的取起，直到不能取为止便得到了最优解。
因此我们非常容易设计出如下算法：
问题初始化；{读入数据}
按Vi从大到小将商品排序；
I:
=1;
repeat
ifM=0thenBreak;{如果卡车满载则跳出循环}
M:
=M-Wi;
ifM>=0then将第I种商品全部装入卡车
else
将（M+Wi）重量的物品I装入卡车;
I:
=I+1;{选择下一种商品}
until（M<=0）OR（I>=N）
在解决上述问题的过程中，首先根据题设条件，找到了贪心选择标准（Vi），并依据这个标准直接逐步去求最优解，这种解题策略被称为贪心法。
ProgramExam25;
ConstFinp='Input.Txt';
Fout='Output.Txt';
VarN,M:
Longint;
S:
Real;
P,W:
Array[1..100]OfInteger;
ProcedureInit;{输出}
VarI:
Integer;
Begin
Assign（Input,Finp）;Reset（Input）;
Readln（M,N）;
ForI:
=1ToNDoReadln（W[I],P[I]）;
Close（Input）;
End;
ProcedureSort（L,R:
Integer）;{按收益值从大到小排序}
VarI,J,Y:
Integer;
X:
Real;
Begin
I:
=L;J:
=R;
X:
=P[（L+R）Div2]/W[（L+R）Div2];
Repeat
While（I=X）DoInc（I）;
While（P[J]/W[J]<=X）And（J>L）DoDec（J）;
IfI<=JThen
Begin
Y:
=P[I];P[I]:
=P[J];P[J]:
=Y;
Y:
=W[I];W[I]:
=W[J];W[J]:
=Y;
Inc（I）;Dec（J）;
End;
UntilI>J;
IfIIfLEnd;
ProcedureWork;
VarI:
Integer;
Begin
Sort（1,N）;
ForI:
=1ToNDo
IfM>=W[I]Then{如果全部可取，则全取}
Begin
S:
=S+P[I];M:
=M-W[I];
End
Else{否则取一部分}
Begin
S:
=S+M*（P[I]/W[I]）;Break;
End;
End;
ProcedureOut;{输出}
Begin
Assign（Output,Fout）;Rewrite（Output）;
Writeln（S:
0:
0）;
Close（Output）;
End;
Begin{主程序}
Init;
Work;
Out;
End.
因此，利用贪心策略解题，需要解决两个问题：
首先，确定问题是否能用贪心策略求解；一般来说，适用于贪心策略求解的问题具有以下特点：
1可通过局部的贪心选择来达到问题的全局最优解。
运用贪心策略解题，一般来说需要一步步的进行多次的贪心选择。
在经过一次贪心选择之后，原问题将变成一个相似的，但规模更小的问题，而后的每一步都是当前看似最佳的选择，且每一个选择都仅做一次。
2原问题的最优解包含子问题的最优解，即问题具有最优子结构的性质。
在背包问题中，第一次选择单位质量最大的货物，它是第一个子问题的最优解，第二次选择剩下的货物中单位重量价值最大的货物，同样是第二个子问题的最优解，依次类推。
其次，如何选择一个贪心标准？
正确的贪心标准可以得到问题的最优解，在确定采用贪心策略解决问题时，不能随意的判断贪心标准是否正确，尤其不要被表面上看似正确的贪心标准所迷惑。
在得出贪心标准之后应给予严格的数学证明。
下面来看看0-1背包问题。
给定一个最大载重量为M的卡车和N种动物。
已知第i种动物的重量为Wi，其最大价值为Vi，设定M，Wi，Vi均为整数，编程确定一个装货方案，使得装入卡车中的所有动物总价值最大。
分析：
对于N种动物，要么被装，要么不装，也就是说在满足卡车载重的条件下，如何选择动物，使得动物价值最大的问题。
即确定一组X1，X2，…，Xn，Xi∈{0,1}
f（x）=max（∑Xi*Vi）其中，∑（Xi*Wi）≦W
从直观上来看，我们可以按照上例一样选择那些价值大，而重量轻的动物。
也就是可以按价值质量比（Vi/Wi）的大小来进行选择。
可以看出，每做一次选择，都是从剩下的动物中选择那些Vi/Wi最大的，这种局部最优的选择是否能满足全局最优呢？
我们来看看一个简单的例子：
设N=3，卡车最大载重量是100，三种动物A、B、C的重量分别是40，50，70，其对应的总价值分别是80、100、150。
情况A：
按照上述思路，三种动物的Vi/Wi分别为2,2,2.14。
显然，我们首先选择动物C，得到价值150，然后任意选择A或B，由于卡车最大载重为100，因此卡车不能装载其他动物。
情况B：
不按上述约束条件，直接选择A和B。
可以得到价值80+100=180，卡车装载的重量为40+50=90。
没有超过卡车的实际载重，因此也是一种可行解，显然，这种解比上一种解要优化。
问题出现在什么地方呢？
我们看看图2-18
从图23中明显可以看出，情况A，卡车的空载率比情况B高。
也就是说，上面的分析，只考虑了货物的价值质量比，而没有考虑到卡车的运营效率，因此，局部的最优化，不能导致全局的最优化。
因此，贪心不能简单进行，而需要全面的考虑，最后得到证明。
例26排队打水问题
有N个人排队到R个水龙头去打水，他们装满水桶的时间为T1，T2，…，Tn为整数且各不相等，应如何安排他们的打水顺序才能使他们花费的时间最少？
分析：
由于排队时，越靠前面的计算的次数越多，显然越小的排在越前面得出的结果越小（可以用数学方法简单证明，这里就不再赘述），所以这道题可以用贪心法解答，基本步骤：
（1）将输入的时间按从小到大排序；
（2）将排序后的时间按顺序依次放入每个水龙头的队列中；
（3）统计，输出答案。
参考程序：
ProgramExam26;
ConstFinp='Input.Txt';
Fout='Output.Txt';
VarA:
Array[1..100]OfInteger;
S:
Array[1..100]OfLongint;
N,M:
Integer;
Min:
Longint;
ProcedureInit;{读入数据}
VarI:
Integer;
Begin
Assign（Input,Finp）;Reset（Input）;
Readln（N,M）;
ForI:
=1ToNDoRead（A[I]）;
Close（Input）;
End;
ProcedureSort（L,R:
Integer）;{将时间从小到大排序}
VarI,J,X,Y:
Integer;
Begin
I:
=L;J:
=R;X:
=A[（L+R）Div2];
Repeat
While（A[I]<=X）And（IWhile（A[J]>=X）And（J>L）DoDec（J）;
IfI<=JThen
Begin
Y:
=A[I];A[I]:
=A[J];A[J]:
=Y;
Inc（I）;Dec（J）;
End;
UntilI>J;
IfLIfR>IThenSort（I,R）;
End;
ProcedureWork;
VarI,J,K:
Integer;
Begin
Fillchar（S,Sizeof（S）,0）;
J:
=0;Min:
=0;
ForI:
=1ToNDo{用贪心法求解}
Begin
Inc（J）;
IfJ=M+1ThenJ:
=1;
S[J]:
=S[J]+A[I];
Min:
=Min+S[J];
End;
Assign（Output,Fout）;Rewrite（Output）;{输出解答}
Writeln（Min）;
Close（Output）;
End;
Begin{主程序}
Init;
Sort（1,N）;
Work;
End.
均分纸牌
有N堆纸牌，编号分别为1，2，…,N。
每堆上有若干张，但纸牌总数必为N的倍数。
可以在任一堆上取若于张纸牌，然后移动。
移牌规则为：
在编号为1堆上取的纸牌，只能移到编号为2的堆上；在编号为N的堆上取的纸牌，只能移到编号为N-1的堆上；其他堆上取的纸牌，可以移到相邻左边或右边的堆上。
现在要求找出一种移动方法，用最少的移动次数使每堆上纸牌数都一样多。
例如N=4，4堆纸牌数分别为：
①9②8③17④6
移动3次可达到目的：
从③取4张牌放到④（981310）->从③取3张牌放到②（9111010）->从②取1张牌放到①（10101010）。
输入格式
N（N堆纸牌，1<=N<=100）
A1A2…An（N堆纸牌，每堆纸牌初始数，l<=Ai<=10000
输出格式OutputFormat
所有堆均达到相等时的最少移动次数。
样例输入
4
98176
样例输出
3
题解：
programzzh;
var
a:
array[1..99]ofinteger;
b,c,d,e,f,g,n,i:
integer;
begin
read（n）;
c:
=0;
forb:
=1tondo
read（a[b]）;
forb:
=1tondo
c:
=c+a[b];
d:
=cdivn;
ifcmodn=0then
begin
fore:
=1ton-1do
ifd<>a[e]then
begin
a[e+1]:
=a[e+1]+a[e]-d;
a[e]:
=d;
f:
=f+1;
end;
write（f）;
end;
end.
金银岛
描述
某天KID利用飞行器飞到了一个金银岛上，上面有许多珍贵的金属，KID虽然更喜欢各种宝石的艺术品，可是也不拒绝这样珍贵的金属。
但是他只带着一个口袋，口袋至多只能装重量为w的物品。
岛上金属有s个种类,每种金属重量不同，分别为n1,n2,...,ns，同时每个种类的金属总的价值也不同，分别为v1,v2,...,vs。
KID想一次带走价值尽可能多的金属，问他最多能带走价值多少的金属。
注意到金属是可以被任意分割的，并且金属的价值和其重量成正比。
输入
第1行是测试数据的组数k，后面跟着k组输入。
每组测试数据占3行，第1行是一个正整数w（1<=w<=10000），表示口袋承重上限。
第2行是一个正整数s（1<=s<=100），表示金属种类。
第3行有2s个正整数，分别为n1,v1,n2,v2,...,ns,vs分别为第一种，第二种，...，第s种金属的总重量和总价值（1<=ni <=10000,1<=vi <=10000）。
输出
k行，每行输出对应一个输入。
输出应精确到小数点后2位。
样例输入
2
50
4
10100503073487100
10000
5
14343323354543548743
样例输出
171.93
508.00
贪心题目，先算出每种金属单价d，按照d进行排序，然后贪心地拣前面几个，直到背包满。
var
a,b:
array[0..100]oflongint;
p:
array[0..100]ofreal;
n,i,j,k,s,m,g:
longint;
tot:
real;
proceduresort（l,r:
longint）;
var
i,j,y:
longint;
x,tt:
real;
begin
i:
=l;
j:
=r;
x:
=p[（l+r）div2];
repeat
whilep[i]inc（i）;
whilexdec（j）;
ifnot（i>j）then
begin
tt:
=p[i];
p[i]:
=p[j];
p[j]:
=tt;
y:
=a[i];
a[i]:
=a[j];
a[j]:
=y;
y:
=b[i];
b[i]:
=b[j];
b[j]:
=y;
inc（i）;
j:
=j-1;
end;
untili>j;
iflsort（l,j）;
ifisort（i,r）;
end;
begin
readln（k）;
forg:
=1tokdo
begin
readln（m）;
readln（s）;
fori:
=1tosdo
begin
read（a[i],b[i]）;
p[i]:
=b[i]/a[i];
end;
tot:
=0;
sort（1,s）;
i:
=s;
while（i>0）and（m>0）do
ifm>=a[i]then
begin
dec（m,a[i]）;
tot:
=tot+b[i];
dec（i）;
end
elsebegintot:
=tot+m*p[i];m:
=0;end;
writeln（tot:
0:
2）;
end;
end.
装箱问题
∙查看
∙提交
∙统计
∙提问
总时间限制:
1000ms
内存限制:
65536kB
描述
一个工厂制造的产品形状都是长方体，它们的高度都是h，长和宽都相等，一共有六个型号，他们的长宽分别为1*1,2*2,3*3,4*4,5*5,6*6。
这些产品通常使用一个6*6*h的长方体包裹包装然后邮寄给客户。
因为邮费很贵，所以工厂要想方设法的减小每个订单运送时的包裹数量。
他们很需要有一个好的程序帮他们解决这个问题从而节省费用。
现在这个程序由你来设计。
输入
输入文件包括几行，每一行代表一个订单。
每个订单里的一行包括六个整数，中间用空格隔开，分别为1*1至6*6这六种产品的数量。
输入文件将以6个0组成的一行结尾。
输出
除了输入的最后一行6个0以外，输入文件里每一行对应着输出文件的一行，每一行输出一个整数代表对应的订单所需的最小包裹数。
样例输入
004001
751000
000000
样例输出
2
1
解题思路
这个问题描述得比较清楚，在这里只解释一下输入输出样例：
共两组有效输入，第一组表示有4
个3X3的产品和1个6X6的产品，此时4个3X3的产品占用一个箱子，另外1个6X6的产品占用一个箱子，所以箱子数是2；第二组表示有7个1X1的产品，5个2X2的产品和1个3X3的产品，可以把它们统统放在一个箱子中，所以输出是1。
分析6个型号的产品占用箱子的具体情况如下：
6X6的产品每个会占用一个完整的箱子，并且没有空余的空间；5X5的产品每个占用一个新的箱子，并且留下11个可以盛放1X1的产品的空余空间；4X4的产品每个占用一个新箱子，并且留下5个可以盛放2X2的产品的空余空间；3X3的产品比较复杂，首先3X3的产品不能放在原来盛放5X5或者4X4的箱子中，那么必须为3X3的产品另开新的箱子，新开的箱子数目等于3X3的产品的数目除以4向上取整；同时需要讨论为3X3的产品新开箱子时，剩余的空间可以盛放多少2X2和1X1的产品（这里如果空间可以盛放2X2的产品，就将它记入2X2的空余空间，等到2X2的产品全部装完，如果还有2X2的空间剩余，再将它们转换成1X1的剩余空间）。
分情况讨论为3X3的产品打开的新箱子额中剩余的空位，共为4种情况：
第一种，3X3的产品的数目正好是4的倍数，所以没有空余空间；第2种，3X3的产品数目是4的倍数加1，这时还剩5个2X2的空位和7个1X1的空位；第3种，3X3的产品数目是4的倍数加2，这时还剩3个2X2的空位和6个1X1的空位；第4种，3X3的产品的数目是4的倍数加3，这时还剩1个2X2的空位和5个1X1的空位；处理完3X3的产品，就可以比较一下剩余的2X2的空位和2X2产品的数目，如果产品数目多，就将2x2的空位全部填满，再为2x2的产品打开新箱子，同时计算新箱子中1x1的空位，如果剩余空位多，就将2x2的产品全部填入2x2的空位，再将剩余的2x2空位转换成1x1的空位；最后处理1x1的产品，比较一下1x1的空位与1x1的产品数目，如果空位多，将1x1的产品全部填入空位，否则，先将1x1的空位填满，然后再为1x1的产品打开新的箱子。
vari,tt,ans,j:
longint;
a:
array[0..6]oflongint;
f:
array[1..6,1..6,0..36]oflongint;
begin
fori:
=1to6do
read（a[i]）;
f[3,2,7]:
=1;
f[3,2,6]:
=1;
f[3,2,5]:
=1;
whilea[1
升级会员 