贪心算法详解

贪心算法详解

贪心算法思想：

顾名思义，贪心算法总是作出在当前看来最好的选择。也就是说贪心算法并不从整体最优考虑，它所作出的选择只是在某种意义上的局部最优选择。当然，希望贪心算法得到的最终结果也是整体最优的。虽然贪心算法不能对所有问题都得到整体最优解，但对许多问题它能产生整体最优解。如单源最短路经问题，最小生成树问题等。在一些情况下，即使贪心算法不能得到整体最优解，其最终结果却是最优解的很好近似。

贪心算法的基本要素：

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

动态规划算法通常以自底向上的方式解各子问题，而贪心算法则通常以自顶向下的方式进行，以迭代的方式作出相继的贪心选择，每作一次贪心选择就将所求问题简化为规模更小的子问题。

对于一个具体问题，要确定它是否具有贪心选择性质，必须证明每一步所作的贪心选择最终导致问题的整体最优解。

2. 当一个问题的最优解包含其子问题的最优解时，称此问题具有最优子结构性质。问题的

最优子结构性质是该问题可用动态规划算法或贪心算法求解的关键特征。

贪心算法的基本思路：

从问题的某一个初始解出发逐步逼近给定的目标，以尽可能快的地求得更好的解。当达到算法中的某一步不能再继续前进时，算法停止。

该算法存在问题：

1. 不能保证求得的最后解是最佳的；

2. 不能用来求最大或最小解问题；

3. 只能求满足某些约束条件的可行解的范围。

实现该算法的过程：

从问题的某一初始解出发；

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种贪心策略，都是无法成立（无法被证明）的，解释如下：

贪心策略：选取价值最大者。反例：

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，则答案错误。但是果在条件中加一句当遇见单位价值相同的时候,优先装重量小的,这样的问题就可以解决.

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

下面我们看一些简单例题。

例24：在N行M列的正整数矩阵中，要求从每行中选出1个数，使得选出的总共N个数的和最大。

分析：要使总和最大，则每个数要尽可能大，自然应该选每行中最大的那个数。因此，我们设计出如下算法:

读入N, M,矩阵数据；

Total := 0;

For I := 1 to N do begin {对N行进行选择}

选择第I行最大的数,记为K；

Total := Total + K；

End；

输出最大总和Total；

从上例中我们可以看出，和递推法相仿，贪心法也是从问题的某一个初始解出发，向给定的目标递推。但不同的是，推进的每一步不是依据某一固定的递推式，而是做一个局部的最优选择，即贪心选择（在例中，这种贪心选择表现为选择一行中的最大整数），这样，不断的将问题归纳为若干相似的子问题，最终产生出一个全局最优解。

特别注意的是是，局部贪心的选择是否可以得出全局最优是能否采用贪心法的关键所在。对于能否使用贪心策略，应从理论上予以证明。下面我们看看另一个问题。

例25：部分背包问题

给定一个最大载重量为M的卡车和N种食品，有食盐，白糖，大米等。已知第i种食品的最多拥有W i公斤，其商品价值为V i元/公斤，编程确定一个装货方案，使得装入卡车中的所有物品总价值最大。

分析：因为每一个物品都可以分割成单位块，单位块的利益越大显然总收益越大，所以它局部最优满足全局最优，可以用贪心法解答，方法如下：先将单位块收益按从大到小进行排列，然后用循环从单位块收益最大的取起，直到不能取为止便得到了最优解。

因此我们非常容易设计出如下算法：

问题初始化；{读入数据}

按V i从大到小将商品排序；

I := 1;

repeat

if M = 0 then Break; {如果卡车满载则跳出循环}

M := M - W i;

if M >= 0 then 将第I种商品全部装入卡车

else

将(M + W i)重量的物品I装入卡车;

I := I + 1; {选择下一种商品}

until (M <= 0) OR (I >= N)

在解决上述问题的过程中，首先根据题设条件，找到了贪心选择标准(V i)，并依据这个标准直接逐步去求最优解，这种解题策略被称为贪心法。

Program Exam25;

Const Finp='Input.Txt';

Fout='Output.Txt';

Var N,M :Longint;

S :Real;

P,W :Array[1..100] Of Integer; Procedure Init; {输出}

Var I :Integer;

Begin

Assign(Input,Finp); Reset(Input);

Readln(M,N);

For I:=1 To N Do Readln(W[I],P[I]);

Close(Input);

End;

Procedure Sort(L,R:Integer); {按收益值从大到小排序}

Var I,J,Y :Integer;

X :Real;

Begin

I:=L; J:=R;

X:=P[(L+R) Div 2]/W[(L+R) Div 2];

Repeat

While (I=X) Do Inc(I);

While (P[J]/W[J]<=X)And(J>L) Do Dec(J);

If I<=J Then

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;

Until I>J;

If I

If L

End;

Procedure Work;

Var I :Integer;

Begin

Sort(1,N);

For I:=1 To N Do

If M>=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;

Procedure Out; {输出}

Begin

Assign(Output,Fout); Rewrite(Output);

Writeln(S:0:0);

Close(Output);

End;

Begin {主程序}

Init;

Work;

Out;

End.

因此，利用贪心策略解题，需要解决两个问题：

首先，确定问题是否能用贪心策略求解；一般来说，适用于贪心策略求解的问题具有以下特点：

①可通过局部的贪心选择来达到问题的全局最优解。运用贪心策略解题，一般来说需

要一步步的进行多次的贪心选择。在经过一次贪心选择之后，原问题将变成一个相似的，但规模更小的问题，而后的每一步都是当前看似最佳的选择，且每一个选择都仅做一次。

②原问题的最优解包含子问题的最优解，即问题具有最优子结构的性质。在背包问题

中，第一次选择单位质量最大的货物，它是第一个子问题的最优解，第二次选择剩下的货物中单位重量价值最大的货物，同样是第二个子问题的最优解，依次类推。

其次，如何选择一个贪心标准？正确的贪心标准可以得到问题的最优解，在确定采用贪心策略解决问题时，不能随意的判断贪心标准是否正确，尤其不要被表面上看似正确的贪心标准所迷惑。在得出贪心标准之后应给予严格的数学证明。

下面来看看0-1背包问题。

给定一个最大载重量为M的卡车和N种动物。已知第i种动物的重量为W i，其最大价值为V i，设定M，W i，V i均为整数，编程确定一个装货方案，使得装入卡车中的所有动物总价值最大。

分析：对于N种动物，要么被装，要么不装，也就是说在满足卡车载重的条件下，如何选择动物，使得动物价值最大的问题。

即确定一组X1，X2，…，Xn， Xi∈{0,1}

f(x)=max(∑X i*V i) 其中，∑(X i*W i)≦W

从直观上来看，我们可以按照上例一样选择那些价值大，而重量轻的动物。也就是可以按价值质量比（V i/W i）的大小来进行选择。可以看出，每做一次选择，都是从剩下的动物中选择那些V i/W i最大的，这种局部最优的选择是否能满足全局最优呢？我们来看看一个简单的例子：

设N=3，卡车最大载重量是100，三种动物A、B、C的重量分别是40，50，70，其对应

的总价值分别是80、100、150。

情况A：按照上述思路，三种动物的V i/W i分别为2,2,2.14。显然，我们首先选择动物C，得到价值150，然后任意选择A或B，由于卡车最大载重为100，因此卡车不能装载其他动物。

情况B：不按上述约束条件，直接选择A和B。可以得到价值80+100=180，卡车装载的重量为40+50=90。没有超过卡车的实际载重，因此也是一种可行解，显然，这种解比上一种解要优化。

问题出现在什么地方呢？我们看看图2-18

图23 卡车装载货物情况分析

从图23中明显可以看出，情况A，卡车的空载率比情况B高。也就是说，上面的分析，只考虑了货物的价值质量比，而没有考虑到卡车的运营效率，因此，局部的最优化，不能导致全局的最优化。

因此，贪心不能简单进行，而需要全面的考虑，最后得到证明。

例26排队打水问题

有N个人排队到R个水龙头去打水，他们装满水桶的时间为T1，T2，…，Tn为整数且各不相等，应如何安排他们的打水顺序才能使他们花费的时间最少？

分析：由于排队时，越靠前面的计算的次数越多，显然越小的排在越前面得出的结果越小（可以用数学方法简单证明，这里就不再赘述），所以这道题可以用贪心法解答，基本步骤：

(1)将输入的时间按从小到大排序；

(2)将排序后的时间按顺序依次放入每个水龙头的队列中；

(3)统计，输出答案。

参考程序：

Program Exam26;

Const Finp='Input.Txt';

Fout='Output.Txt';

Var A :Array[1..100] Of Integer;

S :Array[1..100] Of Longint;

N,M :Integer;

Min :Longint;

Procedure Init; {读入数据}

Var I :Integer;

Begin

Assign(Input,Finp); Reset(Input);

Readln(N,M);

For I:=1 To N Do Read(A[I]);

Close(Input);

End;

Procedure Sort(L,R:Integer); {将时间从小到大排序} Var I,J,X,Y :Integer;

Begin

I:=L; J:=R; X:=A[(L+R) Div 2];

Repeat

While (A[I]<=X)And(I

While (A[J]>=X)And(J>L) Do Dec(J);

If I<=J Then

Begin

Y:=A[I]; A[I]:=A[J]; A[J]:=Y;

Inc(I); Dec(J);

End;

Until I>J;

If L

If R>I Then Sort(I,R);

End;

Procedure Work;

Var I,J,K :Integer;

Begin

Fillchar(S,Sizeof(S),0);

J:=0; Min:=0;

For I:=1 To N Do {用贪心法求解}

Begin

Inc(J);

If J=M+1 Then J:=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 张牌放到④（9 8 13 10）-> 从③取3 张牌放到②（9 11 10 10）-> 从②取1 张牌放到①（10 10 10 10）。

输入格式

N（N 堆纸牌，1 <= N <= 100）

A1 A2 … An （N 堆纸牌，每堆纸牌初始数，l<= Ai <=10000

输出格式Output Format

所有堆均达到相等时的最少移动次数。

样例输入

4

9 8 17 6

样例输出

3

题解：

program zzh;

var

a:array[1..99]of integer;

b,c,d,e,f,g,n,i:integer;

begin

read(n);

c:=0;

for b:=1 to n do

read(a[b]);

for b:=1 to n do

c:=c+a[b];

d:=c div n;

if c mod n=0 then

begin

for e:=1 to n-1 do

if d<>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, ... , n s，同时每个种类的金属总的价值也不同，分别为v1,v2, ..., v s。KID想一次带走价值尽可能多的金属，问他最多能带走价值多少的金属。注意到金属是可以被任意分割的，并且金属的价值和其重量成正比。

输入

第1行是测试数据的组数k，后面跟着k组输入。

每组测试数据占3行，第1行是一个正整数w (1 <= w <= 10000)，表示口袋承重上限。第2

行是一个正整数s (1 <= s <=100)，表示金属种类。第3行有2s个正整数，分别为n1, v1, n2, v2, ... , n s, v s分别为第一种，第二种，...，第s种金属的总重量和总价值(1 <= n i <= 10000, 1 <= v i <= 10000)。

输出

k行，每行输出对应一个输入。输出应精确到小数点后2位。

样例输出

var

a,b:array[0..100] of longint; p:array[0..100] of real;

n,i,j,k,s,m,g:longint;

tot:real;

procedure sort(l,r: longint); var

i,j,y:longint;

x,tt:real;

begin

i:=l;

j:=r;

x:=p[(l+r) div 2];

repeat

while p[i]

inc(i);

while x

dec(j);

if not(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;

until i>j;

if l

sort(l,j);

if i

sort(i,r);

end;

begin

readln(k);

for g:=1 to k do

begin

readln(m);

readln(s);

for i:=1 to s do

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

if m>=a[i] then

begin

dec(m,a[i]);

tot:=tot+b[i];

dec(i);

end

else begin tot:=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以外，输入文件里每一行对应着输出文件的一行，每

一行输出一个整数代表对应的订单所需的最小包裹数。

的倍数，所以没有空余空间；第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的产品打开新的箱子。

var i,tt,ans,j:longint;

a:array[0..6]of longint;

f:array[1..6,1..6,0..36]of longint;

begin

for i:=1 to 6 do

read(a[i]);

f[3,2,7]:=1;

f[3,2,6]:=1;

f[3,2,5]:=1;

while a[1]+a[2]+a[3]+a[4]+a[5]+a[6]<>0 do

begin

ans:=0;

for i:=6 downto 1 do

while a[i]>0 do

begin

inc(ans);

tt:=36-i*i;

dec(a[i]);

for j:=6-i downto 1 do

begin

while (tt>=j*j)and(a[j]>0)and(f[i,j,tt]=0) do

begin

tt:=tt-j*j;

dec(a[j]);

end;

end;

end;

writeln(ans);

for i:=1 to 6 do read(a[i]);

end;

end.

例27：旅行家的预算（NOI99分区联赛第3题）

一个旅行家想驾驶汽车以最少的费用从一个城市到另一个城市（假设出发时油箱时空的）。给定两个城市之间的距离D1、汽车油箱的容量C（以升为单位）、每升汽油能行驶的距离D2、出发点每升汽油价格P和沿途加油站数N（N可以为零），油站i离出发点的距离Di、每升汽油价格Pi（i=1，2，……，N）。

计算结果四舍五入至小数点后两位。

如果无法到达目的地，则输出“No Solution”。

样例：

Input

26.95（该数据表示最小费用）

分析：需要考虑如下问题：

1）出发前汽车的油箱是空的，故汽车必须在起点（1号站）处加油。加多少油？

2）汽车行程到第几站开始加油，加多少油？

可以看出，原问题需要解决的是在哪些油站加油和加多少油的问题。对于某个油站，汽车加油后到达下一加油站，可以归结为原问题的子问题。因此，原问题关键在于如何确定下一个加油站。通过分析，我们可以选择这样的贪心标准：

对于加油站I，下一个加油站J可能第一个是比油站I油价便宜的油站，若不能到达这样的油站，则至少需要到达下一个油站后，继续进行考虑。

对于第一种情况，则油箱需要（d（j）-d（i））/m加仑汽油。对于第二种情况，则需将油箱加满。

贪心算法证明如下：

设定如下变量：

Value[i]：第i个加油站的油价；

Over[i]：在第i站时的剩油；

Way[i]：起点到油站i的距离；

X[I]：X记录问题的最优解，X[I]记录油站I的实际加油量。

首先，X[1]≠0，Over[1]=0。

假设第I站加的X[I]一直开到第K站。则有，X[I]..x[k-1]都为0，而X[K]≠0。

①若Value[I]>Value[k]，则按贪心方案，第I站应加油为

T=（Way[k]-Way[I]）/M-Over[I]。

若T

若T>X[I], 则预示着，汽车开到油站K，仍然有油剩余。假设剩余W加仑汽油，则须费用Value[I]*W，如果W加仑汽油在油站K加，则须费用Value[K]*W，显然Value[K]*W

②若Value[I]

T=C-Over[I] （即加满油）。

若T

若T>X[I]，则表示在第I站的不加满油，而将一部分油留待第K站加，而Value[I]

综合上述分析，可以得出如下算法：

I := 1 {汽车出发设定为第1个加油站}

L := C*D2； {油箱装满油能行驶的距离}

repeat

在L距离以内，向后找第一个油价比I站便宜的加油站J；

if J存在 then

if I站剩余油能到达J then

计算到达J站的剩油

else

在I站购买油，使汽车恰好能到达J站

else

在I站加满油；

I := J； {汽车到达J站}

until 汽车到达终点；

程序如下：

program NOI99L_3;

const

Inp = ‘input.txt’;

Outp = ‘output.txt’;

MaxN = 10001; {最大油站数}

Zero = 1e-16; {误差值}

type

Rectype = record {油站的数据结构}

Value: Real; {油价}

Way: Real; {距起点的距离}

Over: Real; {汽车到达该站时的剩油}

end;

RecPtr = ^Rectype; {油站指针}

var

Oil: array [1 .. MaxN] of RecPtr; {记录所有油站}

D1, {起点到终点之间的距离}

C, {汽车油箱的容量}

D2, {每升汽油能行驶的距离}

N: Integer; {油站数}

Cost: Real; {最小油费}

MaxWay, {满油时汽车最大的行驶距离}

function init: Boolean; {初始化，并判无解}

var

I: Integer;

begin

Read (D1, C, D2);

New(Oil[1]); {处理初始值和起始油站}

Oil[1]^.Way := 0;

Read(Oil[1]^.Value,n);

MaxWay := D2 * C;

for I := 2 to n do begin {读入后N-1个油站信息}

New(Oil[I]);

Readln(Oil[I]^.Way, Oil[I]^.Value);

Oil[I]^.over:=0;

end;

Inc(n); {将终点也看成一个加油站}

New(Oil[n]);

Oil[n]^.Way := D1;

Oil[n]^.Value := 0;

Oil[n]^.over:=0;

for I := 2 to n+1 do {判是否无解}

if (Oil[I]^.Way – Oil[I – 1]^.Way > MaxWay) then begin init:= False;

Exit;

end;

init := True;

end;

procedure Buy(I: Integer; Miles: Real);;

{在I加油站购买Miles/D2加仑汽油}

begin

Cost:= Cost + Miles / D2 * Oil[I]^.Value;

{将买汽油所需的费用加到Cost变量中}

end;

procedure Solve;

var

I, J: Integer;

S: Real;

begin

I := 1; {汽车在起点}

repeat

S := 0.0;

{在MaxWay范围以内，找第一个油价比I站便宜的加油站J}

while (S <= MaxWay+zero) and (J <= N – 1)

and (Oil[I]^.Value <= Oil[J]^.Value) do

begin

Inc(J);

S := S + Oil[J]^.Way – Oil[J – 1]^.Way;

end;

if S <= MaxWay+zero then {如果找到J站或可以直达终点}

{如果剩油足够到达J站，则无需购油，并计算到达J站时汽车的剩油}

if (Oil[I]^.Over + Zero >=Oil[J]^.Way – Oil[I]^.Way) then

Oil[J]^.Over:=Oil[I]^.Over–Oil[J]^.Way+Oil[I]^.Way

else begin

{在I站购买恰好能到达J站的油量}

Buy(I,Oil[J]^.Way – Oil[I]^.Way – Oil[I]^.Over);

Oil[J]^.Over := 0.0;

end

else begin {附近无比I站便宜的加油站J}

Buy(I, MaxWay – Oil[I]^.Over); {在I站加满油}

J := I + 1; {行驶到下一站}

Oil[J]^.Over:= MaxWay – (Oil[J]^.Way – Oil[I]^.Way);

end;

I := J; {汽车直达J站}

until I = N; {汽车到达终点}

end;

begin {主程序}

Cost := 0;

Assign(Input, Inp);

Reset(Input);

Assign(Output, Outp);

Rewrite(Output);

if init then begin {如果有解}

Solve; {求解}

Writeln(Cost:0 :2); {输出最少费用}

end else

Writeln(‘No Solution’); {输出无解}

Close(Input);

Close(Output);

end.

例28：两机器加工问题

有n个部件需在A，B机器上加工，每个工件都必须经过先A后B两道工序。

已知：部件i在A、B机器上的加工时间分别为a i，b i。

问：如何安排n个工件的加工顺序，才能使得总加工时间最短？

输入示例：

N = 5

输出示例：

34 （最少时间）

1 5 4

2

3 （最优加工顺序）

分析：

本题求一个加工顺序使得加工总时间最短，要使时间最短，则就是让机器的空闲时间最短。一旦A机器开始加工，则A机器将会不停的进行作业，关键是B机器在加工过程中，有可能要等待A机器。很明显第一个部件在A机器上加工时，B机器必须等待，最后一个部件在B机器上加工，A机器也在等待B机器的完工。

可以大胆猜想，要使总的空闲的最少，就要把在A机器上加工时间最短的部件最先加工，这样使得B机器能以最快的速度开始加工；把在B机器上加工时间最短的部件放在最后加工。这样使得A机器能尽快的等待B机器完工。于是我们可以设计出这样的贪心法：设M i=min{a i, b i}

将M按照从小到大的顺序排序。然后从第1个开始处理，若M i=a i，则将它排在从头开始的已经作业后面，若M i=b i，则将它排在从尾开始的作业前面。

例如：N=5

（a1，a2，a3，a4，a5）=（3，5，8，7，10）

（b1，b2，b3，b4，b5）=（6，2，1，4，9）

则（m1，m2，m3，m4，m5）=（3，2，1，4，9）

排序之后为（m3，m2，m1，m4，m5）

处理m3：∵m3=b3∴m3排在后面；加入m3之后的加工顺序为（，，，，3）；

处理m2：∵m2=b2∴m2排在后面；加入m2之后的加工顺序为（，，，2，3）；

处理m1：∵m3=a1∴m1排在前面；加入m1之后的加工顺序为（1，，，2，3）；

处理m4：∵m4=b4∴m4排在后面；加入m4之后的加工顺序为（1，，4，2，3）；

处理m5：∵m5=b5∴m5排在后面；加入m5之后的加工顺序为（1，5，4，2，3）；

则最优加工顺序就是（1，5，4，2，3），最短时间为34。显然这是最优解。

问题是这种贪心策略是否正确呢？还需证明。

证明过程如下：

设S={J1，J2，……，J n}，为待加工部件的作业排序，若A机器开始加工S中的部件时，B机器还在加工其它部件，t时刻后再可利用，在这样的条件下，加工S中任务所需的最短时间T（S，t）= min{a i+T(S-{J i},b i+max{t-a i,0})} 其中，J i∈S。

从图24可以看出，（a ）为作业I 等待机器B 的情况，（b ）为机器B 等待作业I 在机器A 上完成的情形。

假设最佳的方案中，先加工作业J i ，然后加工作业J j ，则有：

T(S,t)=a i +T(S-{J i },b i +Max{t-a i ,0})

=a i +a j +T(S-{J i ,J j },b j +max{b i +max{t-a i ,0}-a j ,0})

=a i +a j +T(S-{J i ,J j },T ij )

T ij =b j +max{b i +max{t-a i ,0}-a j ,0}

=b j +b i -a j +max{max{t-a i ,0},a j -b i }

=b i +b j -a j +max{t-a i ,a j -b i ,0}

=b i +b j -a i -a j +max{t,a i ,a i +a j -b i }

?????-+--++=,,

,j

j j i j i j i b a b b a a b b t 若max{t,a i ,a i +a j -b i }=t

若max{t,a i ,a i +a j -b i }=a i 若max{t,a i ,a i +a j -b i }=a i +a j -b i 若将作业J i 和作业J j 的加工顺序，则有：

T’(S,t)=a i +a j +T(S-(J i ,J j ),T ji )，其中

T ji =b i +b j -a i -a j +max{t,a j ,a i +a j -b j }

按假设，因为T<=T ’,所以有:

max{t,ai+aj-bi,ai}<=max{t,ai+aj-bj,aj} ……………… ①

于是有：

a i +a j +max{-

b i ,-a j }<=a i +a j +max{-b j ,-a i }

即

Min{b j ,a i }<=min{b i ,a j } ……………… ②

②式便是Johnson 公式。也就是说②式成立的条件下，任务J i 安排在任务J j 之前加工可以得到最优解。也就是说在A 机器上加工时间短的任务应优先，而在B 机器上加工时间短的任务应排在后面。因此，论证了开始设计的贪心算法是正确的。

算法流程如下：

for I := 1 to N do

{求M 数组}

if A[I] < B[I] then 图24 机器加工作业示意图

M[I] := A[I]

else

M[I] := B[I]；

将M从小到大排序；

S := 1; T := N; {首位指针初始化}

for I := 1 to N do

if 对于第I小的工序J，若A[J] < B[J] then begin

Order[S] := J; {将工序J插在加工序列的前面}

S := S + 1;

end else begin

Order[T] := J; {将工序J插在加工序列的后面}

T := T - 1;

end;

程序如下：

program Machine;

const

Inp = 'input.txt';

Outp = 'output.txt';

MaxN = 100; {最多部件数}

var

N, Min: Integer;

A, B, M,

O, {O用来记录从小到大排序后部件的编号}

Order: array [1 .. MaxN] of Integer; {Order用来记录加工顺序}

procedure Init; {读入数据}

var

I: Integer;

begin

Assign(Input, Inp); Reset(Input);

Readln(N);

for I := 1 to N do

Read(A[I]);

Readln;

for I := 1 to N do

Read(B[I]);

Close(Input);

end;

计算机算法设计与分析习题和答案解析

《计算机算法设计与分析》习题及答案 一．选择题 1、二分搜索算法是利用（A ）实现的算法。 A、分治策略 B、动态规划法 C、贪心法 D、回溯法 2、下列不是动态规划算法基本步骤的是（A ）。 A、找出最优解的性质 B、构造最优解 C、算出最优解 D、定义最优解 3、最大效益优先是（ A ）的一搜索方式。 A、分支界限法 B、动态规划法 C、贪心法 D、回溯法 4. 回溯法解旅行售货员问题时的解空间树是（ A ）。 A、子集树 B、排列树 C、深度优先生成树 D、广度优先生成树 5．下列算法中通常以自底向上的方式求解最优解的是（ B ）。 A、备忘录法 B、动态规划法 C、贪心法 D、回溯法 6、衡量一个算法好坏的标准是（C ）。 A 运行速度快 B 占用空间少 C 时间复杂度低 D 代码短 7、以下不可以使用分治法求解的是（D ）。 A 棋盘覆盖问题 B 选择问题 C 归并排序 D 0/1背包问题 8. 实现循环赛日程表利用的算法是（ A ）。 A、分治策略 B、动态规划法 C、贪心法 D、回溯法 9．下面不是分支界限法搜索方式的是（ D ）。 A、广度优先 B、最小耗费优先 C、最大效益优先 D、深度优先 10．下列算法中通常以深度优先方式系统搜索问题解的是（ D ）。 A、备忘录法 B、动态规划法 C、贪心法 D、回溯法 11.备忘录方法是那种算法的变形。（B ） A、分治法 B、动态规划法 C、贪心法 D、回溯法 12．哈夫曼编码的贪心算法所需的计算时间为（ B ）。 A、O（n2n） B、O（nlogn） C、O（2n） D、O（n） 13．分支限界法解最大团问题时，活结点表的组织形式是（ B ）。 A、最小堆 B、最大堆 C、栈 D、数组 14．最长公共子序列算法利用的算法是（ B ）。 A、分支界限法 B、动态规划法 C、贪心法 D、回溯法 15．实现棋盘覆盖算法利用的算法是（ A ）。 A、分治法 B、动态规划法 C、贪心法 D、回溯法 16.下面是贪心算法的基本要素的是（ C ）。 A、重叠子问题 B、构造最优解 C、贪心选择性质 D、定义最优解 17.回溯法的效率不依赖于下列哪些因素（ D ） A.满足显约束的值的个数 B. 计算约束函数的时间 C.计算限界函数的时间 D. 确定解空间的时间 18.下面哪种函数是回溯法中为避免无效搜索采取的策略（ B ） A．递归函数 B.剪枝函数C。随机数函数 D.搜索函数 19. （ D ）是贪心算法与动态规划算法的共同点。

贪心算法经典例题

贪心算法经典例题 发布日期：2009-1-8 浏览次数：1180 本资料需要注册并登录后才能下载！ ·用户名密码验证码找回密码·您还未注册？请注册 您的账户余额为元，余额已不足，请充值。 您的账户余额为元。此购买将从您的账户中扣除费用0.0元。 内容介绍>> 贪心算法经典例题 在求最优解问题的过程中，依据某种贪心标准，从问题的初始状态出发，直接去求每一步的最优解，通过若干次的贪心选择，最终得出整个问题的最优解，这种求解方法就是贪心算法。 从贪心算法的定义可以看出，贪心法并不是从整体上考虑问题，它所做出的选择只是在某种意义上的局部最优解，而由问题自身的特性决定了该题运用贪心算法可以得到最优解。 我们看看下面的例子 例1 均分纸牌（NOIP2002tg） [问题描述] 有 N 堆纸牌，编号分别为 1，2，…, N。每堆上有若干张，但纸牌总数必为 N 的倍数。可以在任一堆上取若干张纸牌，然后移动。移牌规则为：在编号为 1 堆上取的纸牌，只能移到编号为 2 的堆上；在编号为 N 的堆上取的纸牌，只能移到编号为 N-1 的堆上；其他堆上取的纸牌，可以移到相邻左边或右边的堆上。现在要求找出一种移动方法，用最少的移动次数使每堆上纸牌数都一样多。例如 N=4，4 堆纸牌数分别为： ①9 ②8 ③17 ④ 6 移动3次可达到目的： 从③取 4 张牌放到④（9 8 13 10） -> 从③取 3 张牌放到②（9 11 10 10）-> 从②取 1 张牌放到①（10 10 10 10）。 [输入]：键盘输入文件名。 文件格式：N（N 堆纸牌，1 <= N <= 100） A1 A2 … An （N 堆纸牌，每堆纸牌初始数，l<= Ai <=10000） [输出]：输出至屏幕。格式为：所有堆均达到相等时的最少移动次数。 [输入输出样例] a.in： 4 9 8 17 6 屏慕显示：3 算法分析：设a[i]为第i堆纸牌的张数（0<=i<=n），v为均分后每堆纸牌的张数，s为最小移到次数。 我们用贪心法，按照从左到右的顺序移动纸牌。如第i堆(0

贪心算法详解分析

贪心算法详解 贪心算法思想： 顾名思义，贪心算法总是作出在当前看来最好的选择。也就是说贪心算法并不从整体最优考虑，它所作出的选择只是在某种意义上的局部最优选择。当然，希望贪心算法得到的最终结果也是整体最优的。虽然贪心算法不能对所有问题都得到整体最优解，但对许多问题它能产生整体最优解。如单源最短路经问题，最小生成树问题等。在一些情况下，即使贪心算法不能得到整体最优解，其最终结果却是最优解的很好近似。 贪心算法的基本要素： 1.贪心选择性质。所谓贪心选择性质是指所求问题的整体最优解可以通过一系列局部最优的选择，即贪心选择来达到。这是贪心算法可行的第一个基本要素，也是贪心算法与动态规划算法的主要区别。 动态规划算法通常以自底向上的方式解各子问题，而贪心算法则通常以自顶向下的方式进行，以迭代的方式作出相继的贪心选择，每作一次贪心选择就将所求问题简化为规模更小的子问题。 对于一个具体问题，要确定它是否具有贪心选择性质，必须证明每一步所作的贪心选择最终导致问题的整体最优解。 2. 当一个问题的最优解包含其子问题的最优解时，称此问题具有最优子结构性质。问题的 最优子结构性质是该问题可用动态规划算法或贪心算法求解的关键特征。 贪心算法的基本思路： 从问题的某一个初始解出发逐步逼近给定的目标，以尽可能快的地求得更好的解。当达到算法中的某一步不能再继续前进时，算法停止。 该算法存在问题： 1. 不能保证求得的最后解是最佳的； 2. 不能用来求最大或最小解问题； 3. 只能求满足某些约束条件的可行解的范围。 实现该算法的过程： 从问题的某一初始解出发； while 能朝给定总目标前进一步do 求出可行解的一个解元素； 由所有解元素组合成问题的一个可行解； 用背包问题来介绍贪心算法： 背包问题：有一个背包，背包容量是M=150。有7个物品，物品可以分割成任意大小。要 求尽可能让装入背包中的物品总价值最大，但不能超过总容量。

贪心算法解决活动安排问题报告

1.引言： 贪心法是一种改进了的分级处理方法。用贪心法设计算法的特点是一步一步地进行，每一步上都要保证能获得局部最优解。每一步只考虑一个数据，它的选取满足局部优化条件。若下一个数据与部分最优解连在一起不再是可行解时，就不把该数据添加到部分解中，直到把所有数据枚举完，或者不能再添加为止。这种能够得到某种度量意义下的最优解的分级处理方法称为贪心法。 贪心算法总是做出在当前看来是最优的选择，也就是说贪心算法并不是从整体上加以考虑，它所做出的选择只是在某种意义上的局部最优解，而许多问题自身的特性决定了该题运用贪心算法可以得到最优解或较优解。 2.贪心算法的基本思想及存在问题 贪心法的基本思想： 从问题的某一个初始解出发逐步逼近给定的目标，以尽可能快的地求得更好的解。当达到某算法中的某一步不能再继续前进时，算法停止。 1.建立数学模型来描述问题。 2.把求解的问题分成若干个子问题。 3.对每一子问题求解，得到子问题的局部最优解。 4.把子问题的解局部最优解合成原来解问题的一个解。 3.活动安排问题： 3.1 贪心算法解决活动安排问题 学校举办活动的安排问题是用贪心算法有效求解的一个很好例子。活动安排问题要求安排一系列争用某一公共资源的活动。用贪心算法可使尽可能多的活动能兼容的使用公共资源。设有n个活动的集合｛0，1，2，…，n-1｝，其中每个活动都要求使用同一资源，如会场等，而在同一时间内只有一个活动能使用这一资源。每个活动i都有一个要求使用该资源的起始时间starti和一个结束时间endi，且starti

2009.1算法设计与分析课程期末试卷-A卷(自测 )

华南农业大学期末考试试卷（A卷）2008学年第一学期考试科目：算法分析与设计 考试类型：（闭卷）考试时间：120 分钟 学号姓名年级专业 一、选择题（20分，每题2分） 1.下述表达不正确的是。 A．n2/2 + 2n的渐进表达式上界函数是O(2n) B．n2/2 + 2n的渐进表达式下界函数是Ω(2n) C．logn3的渐进表达式上界函数是O(logn) D．logn3的渐进表达式下界函数是Ω(n3) 2.当输入规模为n时，算法增长率最大的是。 A．5n B．20log 2n C．2n2 D．3nlog 3 n 3.T（n）表示当输入规模为n时的算法效率，以下算法效率最优的是。A．T（n）= T（n – 1）+1，T（1）=1 B．T（n）= 2n2 C．T（n）= T（n/2）+1，T（1）=1 D．T（n）= 3nlog 2 n 4.在棋盘覆盖问题中，对于2k×2k的特殊棋盘（有一个特殊方块），所需的L型骨 牌的个数是。 A．（4k– 1）/3 B．2k /3 C．4k D．2k 5.在寻找n个元素中第k小元素问题中，若使用快速排序算法思想，运用分治算

法对n个元素进行划分，应如何选择划分基准？下面答案解释最合理。 A．随机选择一个元素作为划分基准 B．取子序列的第一个元素作为划分基准 C．用中位数的中位数方法寻找划分基准 D．以上皆可行。但不同方法，算法复杂度上界可能不同 6.有9个村庄，其坐标位置如下表所示： 现在要盖一所邮局为这9个村庄服务，请问邮局应该盖在才能使到邮局到这9个村庄的总距离和最短。 A．（4.5，0）B．（4.5，4.5）C．（5，5）D．（5，0） 7.n个人拎着水桶在一个水龙头前面排队打水，水桶有大有小，水桶必须打满水， 水流恒定。如下说法不正确？ A．让水桶大的人先打水，可以使得每个人排队时间之和最小 B．让水桶小的人先打水，可以使得每个人排队时间之和最小 C．让水桶小的人先打水，在某个确定的时间t内，可以让尽可能多的人打上水D．若要在尽可能短的时间内，n个人都打完水，按照什么顺序其实都一样 8.分治法的设计思想是将一个难以直接解决的大问题分割成规模较小的子问题， 分别解决子问题，最后将子问题的解组合起来形成原问题的解。这要求原问题和子问题。

贪 心 算 法

【贪心算法】思想 & 基本要素 & 贪心算法与局部最优 & 贪心算法与动态规划的区别 & 运用贪心算法求解问题 首先我们先代入问题来认识一下贪心算法涉及的问题 找钱问题 给顾客找钱，希望找零的钞票尽可能少，零钱种类和数量限定 找钱问题满足最优子结构 最快找零（贪心）：为得到最小的找零次数，每次最大程度低减少零额活动安排问题 设个活动都需要使用某个教室，已知它们的起始时间和结束时间，求合理的安排使得举行的活动数量最多 贪心：使得每次安排后，教室的空闲时间最多 解决过程如下： 贪心算法求得的相容活动集是最大的 第一步：证明最优解中包含结束时间最早的活动 设相容集 A 是一个最优解，其结束最早的活动为 a，则 ( A - { a }) U { 1 } 也是一个最优解 第二步：证明去掉结束时间最早的活动后，得到的子问题仍是最优的：反证法 理解贪心算法 贪心算法总是做出当前最好的选择 贪心选择的依据是当前的状态，而不是问题的目标

贪心选择是不计后果的 贪心算法通常以自顶向下的方法简化子问题 贪心算法求解的问题具备以下性质 贪心选择性质：问题的最优解可以通过贪心选择实现 最优子结构性质：问题的最优解包含子问题的最优解 贪心选择性质的证明 证明问题的最优解可以由贪心选择开始 即第一步可贪心 证明贪心选择后得到的子问题满足最优子结构 即步步可贪心 背包问题 问题描述：给定 n 个物品和一个背包。物品 i 的重量为 Wi ，价值为 Vi ，背包的容量为 c ，问如何选择物品或物品的一部分，使得背包中物品的价值最大？ 当 n = 3 ，c = 50 0-1背包问题：装入物品2、3，最大价值220 背包问题：装入物品1、2和2-3的物品3，最大价值240（贪心算法）贪心算法无法求解0-1背包问题，按贪心算法，0-1背包问题将装入物品1和2 贪心与局部最优 思考：为什么0-1背包可以用动态规划？而不能用贪心算法 贪心易陷入局部最优

贪心算法与动态规划的比较

贪心算法与动态规划的比较 【摘要】介绍了计算机算法设计的两种常用算法思想：贪心算法与动态规划算法。通过介绍两种算法思想的基本原理，比较两种算法的联系和区别。通过背包问题对比了两种算法的使用特点和使用范围。 【关键字】动态规划；贪心算法；背包问题 1、引言 为了满足人们对大数据量信息处理的渴望，为解决各种实际问题，计算机算法学得到了飞速的发展，线性规划、动态规划、贪心策略等一系列运筹学模型纷纷运用到计算机算法学中，产生了解决各种现实问题的有效算法。虽然设计一个好的求解算法更像是一门艺术而不像是技术，但仍然存在一些行之有效的、能够用于解决许多问题的算法设计方法，你可以使用这些方法来设计算法，并观察这些算法是如何工作的。一般情况下，为了获得较好的性能，必须对算法进行细致的调整。但是在某些情况下，算法经过调整之后性能仍无法达到要求，这时就必须寻求另外的方法来求解该问题。本文针对部分背包问题和0/ 1 背包问题进行分析，介绍贪心算法和动态规划算法的区别。 2、背包问题的提出 给定n种物品( 每种物品仅有一件) 和一个背包。物品i的重量是w i，其价值为p i，背包的容量为M。问应如何选择物品装入背包，使得装入背包中的物品的总价值最大,每件物品i的装入情况为x i，得到的效益是p i*x i。 ⑴部分背包问题。在选择物品时，可以将物品分割为部分装入背包，即0≤x i≤1 ( 贪心算法)。 ⑵0/ 1背包问题。和部分背包问题相似，但是在选择物品装入时要么不装，要么全装入，即x i = 1或0。( 动态规划算法) 。 3、贪心算法 3.1 贪心算法的基本要素 能够使用贪心算法的许多例子都是最优化问题，每个最优化问题都包含一组限制条件和一个优化函数，符合限制条件的问题求解方案称为可行解；使优化函数取得最佳值的可行解称为最优解。此类所求问题的整体最优解可以通过一系列局部最优的选择，即贪心选择来达到(这是贪心算法与动态规划的主要区别) 。 3.2贪心策略的定义 贪心策略是指从问题的初始状态出发，通过若干次的贪心选择而得出最优值( 或较优解) 的一种解题方法。贪心策略总是做出在当前看来是最优的选择，也就是说贪心策略并不是从整体上加以考虑，它所做出的选择只是在某种意义上的局部最优解，而许多问题自身的特性决定了该问题运用贪心策略可以得到最优解或较优解。(注：贪心算法不是对所有问题都能

贪心算法求解最优服务次序问题

实验名称：贪心算法实例编程 求解最优服务次序问题 1、实验目的： 1)理解贪心算法的概念 2)掌握贪心算法的基本要素 3)掌握设计贪心算法的一般步骤 4)针对具体问题，能应用贪心算法设计有效算法 5)用C++实现算法，并且分析算法的效率 2、实验设备及材料： 硬件设备：PC机 机器配置：双核cpu频率2.2GHz,内存2G 操作系统：Windows 7 开发工具：VC++6.0 3、实验内容： ①问题描述 设有n个顾客同时等待一项服务。顾客i需要的服务时间为t i，1≤i≤n。 应如何安排n个顾客的服务次序才能使平均等待时间达到最小？平均等待时间是n恶搞顾客等待服务时间的总和除以n。 ②编程任务 对于给定的n个顾客需要的服务时间，计算最优服务次序。 ③样例 例如，现在有5个顾客，他们需要的服务时间分别为：56，12，5，99，33。 那么，按照所需服务时间从小到大排序为：5,12,33,56,99。排序后的顾客等待服务完成的时间为：5，17，50，106，205；和为：383；平均等待时间为：76.6。

4、实验方法步骤及注意事项： ①实验步骤 a、分析问题，确定最优的贪心选择； b、针对贪心选择过程进行算法设计； c、举例验证算法的正确性； d、上机调试算法。 ②解题思路 1)求解最优服务次序问题的贪心策略为：先为所需服务时间最短的顾客服务。 2)使用贪心算法求解最优服务次序问题的算法，用C++语言描述。 ①.最优值：(贪心算法) text(int n,int x[],int s[])//s[]为保存每个顾客等待时间的数组 { int i; int sum=0; for(i=0;i0){ s[i]=x[i]+s[i-1]; sum+=s[i];} else { s[i]=x[i]; sum+=s[i]; } } return sum/n; } ②.最优解：（快速排序） void QuickSort(int e[], int first, int end) { int i=first,j=end,key=e[first]; while(i=key) j--; e[i]=e[j]; while(ii+1) QuickSort(e,i+1,end); }

贪心算法

贪心算法的基本思想是找出整体当中每个小的局部的最优解，并且将所有的这些局部最优解合起来形成整体上的一个最优解。因此能够使用贪心算法的问题必须满足下面的两个性质： 1.整体的最优解可以通过局部的最优解来求出； 2.一个整体能够被分为多个局部，并且这些局部都能够求出最优解。使用贪心算法当中的两个典型问题是活动安排问题和背包问题。 在对问题求解时，总是作出在当前看来是最好的选择。也就是说，不从整体上加以考虑，它所作出的仅仅是在某种意义上的局部最优解（是否是全局最优，需要证明）。 特别注意：若要用贪心算法求解某问题的整体最优解，必须首先证明贪心思想在该问题的应用结果就是最优解！！ 以经典的活动安排为例： 1、若A是E的最优解，那么E-A 也是问题的最优解，在余下的问题里，继续拿最早结束的； 2、拿可以开始的最早结束。(所以要按结束时间排序一次，然后把可以开始的选择上，然后继续向后推) 贪心子结构是独立的（往往用标志判断而已），不同于动态规划（后面每一边的计算要用到前一步的值，另外开辟空间来保存） 贪心算法的基本步骤： 1、从问题的某个初始解出发。 2、采用循环语句，当可以向求解目标前进一步时，就根据局部最优策略，得到一个部分解，缩小问题的范围或规模。 3、将所有部分解综合起来，得到问题的最终解。 如最经典的活动安排问题，按结束时间从小到大排序，这样找出第一个节目后，剩下的节目已经是最safe的子结构了，再从子结构中最最早结束但又不和上一次观看的节目有冲突的节目 void arrange(int s[],int f[],bool A[],int n) { A[0] = true; int lastSelected = 0; for (int i = 1;i

数据结构课设_TSP贪心算法

数据结构课程设计 设计说明书 题目 TSP问题贪心算法 起止日期：2014年11月10 日至2014 年11月17日 计算机科学与工程学院 2014年11月9日

课程设计任务书 一、设计目的 熟悉各种数据结构和运算，会使用数据结构的基本操作解决一些实际问题。二、设计要求 在本课程设计过程中要求学生： （1）重视课程设计环节，用严谨、科学和踏实的工作态度对待课程设计的每一项任务； （2）按照课程设计的题目要求，独立地完成各项任务，严禁抄袭；凡发现抄袭，抄袭者与被抄袭者皆以零分计入本课程设计成绩。凡发现实验报告或源程序雷同，涉及的全部人员皆以零分计入本课程设计成绩。 （3）学生在接受设计任务后，根据要求认真完成。 （4）认真编写课程设计报告。 三、设计内容 TSP问题（贪心法求解） 1) 问题描述 所谓TSP问题是指旅行家要旅行n个城市，要求各个城市经历且仅经历一次，并要求所走的路程最短。该问题又称为货郎担问题、邮递员问题、售货员问题，是图问题中最广为人知的问题。 2) 基本要求 (1) 上网查找TSP问题的应用实例； (2) 分析求TSP问题的全局最优解的时间复杂度； (3) 设计一个求近似解的算法； (4) 分析算法的时间复杂度。 3) 设计思想 对于TSP问题，一种最容易想到的也肯定能得到最佳解的算法是穷举法，即考虑所有可能的旅行路线，从中选择最佳的一条。但是用穷举法求解TSP问题的时间复杂度为Ο(n!)，当n大到一定程度后是不可解的。

4）设计思想 对于TSP问题，一种最容易想到的也肯定能得到最佳解的算法是穷举法，即考虑所有可能的旅行路线，从中选择最佳的一条。但是用穷举法求解TSP问题的时间复杂度为Ο(n!)，当n 大到一定程度后是不可解的。 本实验只要求近似解，可以采用贪心法求解：任意选择某个城市作为出发点，然后前往最近的未访问的城市，直到所有的城市都被访问并且仅被访问一次，最后返回到出发点。 为便于查找离某顶点最近的邻接点，可以采用邻接矩阵存储该图。算法用伪代码描述如下： 1. 任意选择某个顶点v作为出发点； 2. 执行下述过程，直到所有顶点都被访问： 2.1 v=最后一个被访问的顶点； 2.2 在顶点v的邻接点中查找距离顶点v最近的未被访问的邻接点j； 2.2 访问顶点j； 3. 从最后一个访问的顶点直接回到出发点v； 四、参考文献 1. 王红梅，数据结构，清华大学出版社； 2. 王红梅，数据结构学习辅导与实验指导，清华大学出版社； 3. 王晓东，计算机算法设计与分析，电子工业出版社。

算法设计与分析实验报告贪心算法

算法设计与分析实验报告 贪心算法 班级：2013156 学号：201315614 ：春阳哈夫曼编码 代码 #include float small1,small2; int flag1,flag2,count; typedef struct HuffmanTree { float weight; int lchild,rchild,parent; }huffman; huffman huffmantree[100]; void CreatHuffmanTree(int n,int m) { int i; void select(); printf("请输入%d个节点的权值:",n); for(i=0;i

贪心算法练习题

贪心算法 1.喷水装置（一） 描述 现有一块草坪，长为20米，宽为2米，要在横中心线上放置半径为Ri的喷水装置，每个喷水装置的效果都会让以它为中心的半径为实数Ri(0

对于每一组输入，输出最多能够安排的活动数量。 每组的输出占一行 样例输入 2 2 1 10 10 11 3 1 10 10 11 11 20 样例输出 1 2 提示注意：如果上一个活动在T时间结束，下一个活动最早应该在T+1时间开始。 解题思路：这是一个贪心法中选择不相交区间的问题。先对活动结束时间从小到大排序，排序的同时活动的起始时间也要跟着变化。而且，结束时间最小的活动一定会安排，不然这段时间就白白浪费了。后一个活动的起始时间如果比前一个活动的结束时间大，即两个活动没有相交时间，就把这个活动也安排上。就这样一直找到结束时间最大的，输出时间数目即可。排序时可用下面的方法，排序的同时起始时间也跟着变了。 如果输入 0 6 3 4 1 9 2 8 则排序后的结果就是 3 4 0 6 2 8 1 9 Sample Output 3 5

大学计算机基础mooc习题集整理(含答案解析)

大学计算机考试模拟题（理工类） 一、简答题（本题共6个小题，每小题5分，共30分） 1. 什么是信息社会？信息社会的主要特征是什么？P32 第4题参见P13 P14 2. 什么是CPU，简述CPU的基本组成和功能P108 第18.(1) 参见P77 3. 什么是操作系统？简述操作系统的主要功能。P109 第24题参见P89 4. 人类问题求解的一般思维过程是什么？简要说明参见P112图3-1 描述 5. 什么是枚举法？说明枚举法的优缺点。参见P113第6段, P132穷举法 6. 什么是浏览器/服务器（B/S）三层体系结构，画图并简要说明。P340第10题参见P316 P276 二、单项选择题（本题共20个小题，每小题1分，共20分） 1. 下列容不属于信息素养（Information Literacy）的是 A．信息意识B．信息知识 C．分析能力D．信息道德 2. 阿兰·麦席森·图灵（Alan Mathison Turing）对计算机科学的发展做出了巨大贡献，下列说法不正确的是 A．图灵是著名的数学家、逻辑学家、密码学家，被称为计算机科学之父。 B．图灵最早提出关于机器思维的问题，被称为人工智能之父。 C．图灵创立了二进制。 D．“图灵奖”是为奖励那些对计算机科学研究与推动计算机技术发展有卓越贡献的杰出科学家而设立的。 3. 最早的机械式计算机“加法器”的发明人是 A．帕斯卡B．巴贝奇 C．莱布尼茨D．布尔 4. 巴贝奇的“分析机”到他终生都没有制造出来，下列说确的是（）

A．设计原理有错误B．设计精度不够 C．设计图纸不够完善D．机械加工的工艺水平达不到它要求的精度 5. 以集成电路为基本元件的第三代计算机出现的时间为（）。A．1965—1969B．1964—1975 C．1960—1969D．1950—1970 6. 在计算机中，引入16进制，主要目的是（）。 A．计算机中的数据存储采用16进制 B．计算机中的数据运算采用16进制 C．缩短2进制字串的长度 D．计算机的存地址采用16进制编制 7. 设计算机字长为16位，采用补码表示，可表示的整数的取值围是（）。A．0～65535B．-32767～32767 C．-32768～32767D．-32767～32768 8. 下列叙述中，正确的是( )。 A．所有十进制小数都能准确地转换为有限位二进制小数 B．汉字的计算机码就是国标码 C．所有二进制小数都能准确地转换为十进制小数 D．存储器具有记忆能力，其中的信息任何时候都不会丢失 9. 关于微处理器，下列说法错误的是（） A、微处理器就是微机的CPU，由控制器运算器和存储器组成。 B、微处理器不包含存储器。 C、微处理器执行CPU控制部件和算术逻辑部件的功能。 D、微处理器与存储器和外围电路芯片组成微型计算机。 10. 关于操作系统，下列叙述中正确的是（）。

贪心算法的应用实例

贪心算法的应用实例 例2．排队问题 【题目描述】 在一个医院B 超室，有n个人要做不同身体部位的B超，已知每个人需要处理的时间为ti，（00,从而新的序列比原最优序列好，这与假设矛盾，故s1为最小时间，同理可证s2…sn依次最小。 例3．:数列极差问题 【题目描述】 在黑板上写了N个正整数做成的一个数列，进行如下操作：每一次擦去其中的两个数a 和b，然后在数列中加入一个数a×b+1，如此下去直至黑板上剩下一个数，在所有按这种操作方式最后得到的数中，最大的max，最小的为min，则该数列的极差定义为M=max-min。 编程任务：对于给定的数列，编程计算出极差M。 输入输出样例： 输入： 4 2 1 4 3 输出： 13 【算法分析】 当看到此题时，我们会发现求max与求min是两个相似的过程。若我们把求解max与min的过程分开，着重探讨求max的问题。 下面我们以求max为例来讨论此题用贪心策略求解的合理性。 讨论：假设经（Ｎ－3）次变换后得到３个数：a ,b , max＇（max＇≥ａ≥ｂ），其中max＇是（Ｎ－２）个数经（Ｎ－３）次ｆ变换后所得的最大值，此时有两种求值方式，设其所求值分别为 z1，z2，则有：z1＝(ａ×ｂ＋１）×max＇＋１，z2＝(ａ×max＇＋１）×ｂ+１所以z1－z2＝max＇－ｂ≥０若经（Ｎ－２）次变换后所得的３个数为：ｍ，ａ，

贪心算法结课论文

贪心算法求解汽车加油问题 1 引言 随着科学的发展，人们生活中面临的大数据量越来越多。生活的快节奏要求人们对这些庞大的数据进行简单快速的处理，在这种实际需求的背景下，计算机算法设计得到了飞速发展，线性规划、动态规划、贪心策略等一系列运筹学模型越来越多被应用到计算机算法学中。 当一个问题具有最优子结构性质和贪心选择性质时，可用动态规划法来解决。但是贪心算法通常会给出一个更简单、直观和高效的解法。贪心算法通过一系列的选择来得到一个问题的解。尽管贪心算法对许多问题不能总是产生整体最优解，但对诸如最短路径问题、最小生成树问题，以及哈夫曼编码问题等具有最优子结构和贪心选择性质的问题却可以获得整体最优解，而且所给出的算法一般比动态规划算法更加简单、直观和高效[1]。 2 贪心算法 2.1 贪心算法概述 贪心算法又称贪婪算法，是指在求解问题时，总是做出在当前看来是最好的选择，也就是说，贪心算法并不要求从整体上最优考虑，它所作的仅是在某种意义上的局部最优选择。当然，希望贪心算法得到的最终结果也是整体最优的。贪心算法并不是对所有问题都能得到整体最优解，但对范围相当广泛的许多问题它能产生整体最优解或者是整体最优解的近似解。 贪心算法可以简单描述为：对一组数据进行排序，找出最小值，进行处理，再找出最小值，再处理。也就是说贪心算法是一种在每一步选择中都采取在当前状态下最好或最优的选择，从而希望得到结果是最好或最优的算法。 贪婪算法是一种对某些求最优解问题的更简单、更迅速的设计技术。用贪婪法设计算法的特点是一步一步地进行，常以当前情况为基础根据某个优化测度作最优选择，而不考虑各种可能的整体情况，它省去了为找最优解要穷尽所有可能而必须耗费的大量时间，它采用自顶向下,以迭代的方法做出相继的贪心选择,每做一次贪心选择就将所求问题简化为一个规模更小的子问题, 通过每一步贪心选择,可得到问题的一个最优解，虽然每一步上都要保证能获得局部最优解，但由此产生的全局解有时不一定是最优的。 贪婪算法是一种改进了的分级处理方法。其核心是根据题意选取一种量度标准。然后将这多个输入排成这种量度标准所要求的顺序，按这种顺序一次输入一个量。如果这个输入和当前已构成在这种量度意义下的部分最佳解加在一起不能产生一个可行解，则不把此输入加到这部分解中。这种能够得到某种量度意义下最优解的分级处理方法称为贪婪算法。 对于一个给定的问题，往往可能有好几种量度标准。初看起来，这些量度标准似乎都是可取的，但实际上，用其中的大多数量度标准作贪婪处理所得到该量度意义下的最优解并不是问题的最优解，而是次优解。因此，选择能产生问题最优解的最优量度标准

智能算法30个案例分析

智能算法30个案例分析 【篇一：智能算法30个案例分析】 智能算法是我们在学习中经常遇到的算法，主要包括遗传算法，免 疫算法，粒子群算法，神经网络等，智能算法对于很多人来说，既 爱又恨，爱是因为熟练的掌握几种智能算法，能够很方便的解决我 们的论坛问题，恨是因为智能算法感觉比较“玄乎”，很难理解，更 难用它来解决问题。 因此，我们组织了王辉，史峰，郁磊，胡斐四名高手共同写作 matlab 智能算法，该书包含了遗传算法，免疫算法，粒子群算法， 鱼群算法，多目标pareto 算法，模拟退火算法，蚁群算法，神经网络，svm 等，本书最大的特点在于以案例为导向，每个案例针对一 个实际问题，给出全部程序和求解思路，并配套相关讲解视频，使 读者在读过一个案例之后能够快速掌握这种方法，并且会套用案例 程序来编写自己的程序。本书作者在线，读者和会员可以向作者提问，作者做到有问必答。 本书和目录如下：基于遗传算法的tsp算法（王辉） tsp (旅行商问题—traveling salesman problem)，是典型的np 完全问题，即其 最坏情况下的时间复杂性随着问题规模的增大按指数方式增长，到 目前为止不能找到一个多项式时间的有效算法。遗传算法是一种进 化算法，其基本原理是仿效生物界中的“物竞天择、适者生存” 的演 化法则。遗传算法的做法是把问题参数编码为染色体，再利用迭代 的方式进行选择、交叉以及变异等运算来交换种群中染色体的信息，最终生成符合优化目标的染色体。实践证明，遗传算法对于解决 tsp 问题等组合优化问题具有较好的寻优性能。 基于遗传算法和非线性规划的函数寻优算法（史峰）遗传算法提供 了求解非线性规划的通用框架，它不依赖于问题的具体领域。遗传 算法的优点是将问题参数编码成染色体后进行优化，而不针对参数 本身，从而不受函数约束条件的限搜索过程从问题解的一个集合开始，而不是单个个体，具有隐含并行搜索特性，大大减少陷入局部 最小的可能性。而且优化计算时算法不依赖于梯度信息，且不要求 目标函数连续及可导，使其适于求解传统搜索方法难以解决的大规模、非线性组合优化问题。 用于模式分类、模式识别等方面．但 bp 算法收敛速度慢，且很容易 陷入局部极小点，而遗传算法具有并行搜索、效率高、不存在局部

贪心算法的实际应用

贪心算法的实际应用 姓名： 班级： 学号： 指导老师：

定义： 贪心算法（又称贪婪算法）是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的仅是在某种意义上的局部最优解。贪心算法不是对所有问题都能得到整体最优解，但对范围相当广泛的许多问题他能产生整体最优解或者是整体最优解的近似解。 贪婪算法（Greedy algorithm）是一种对某些求最优解问题的更简单、更迅速的设计技术。用贪婪法设计算法的特点是一步一步地进行，常以当前情况为基础根据某个优化测度作最优选择，而不考虑各种可能的整体情况，它省去了为找最优解要穷尽所有可能而必须耗费的大量时间，它采用自顶向下，以迭代的方法做出相继的贪心选择，每做一次贪心选择就将所求问题简化为一个规模更小的子问题，通过每一步贪心选择，可得到问题的一个最优解，虽然每一步上都要保证能获得局部最优解，但由此产生的全局解有时不一定是最优的，所以贪婪法不要回溯。 贪婪算法是一种改进了的分级处理方法。其核心是根据题意选取一种量度标准。然后将这多个输入排成这种量度标准所要求的顺序，按这种顺序一次输入一个量。如果这个输入和当前已构成在这种量度意义下的部分最佳解加在一起不能产生一个可行解，则不把此输入加到这部分解中。这种能够得到某种量度意义下最优解的分级处理方法称为贪婪算法。 对于一个给定的问题，往往可能有好几种量度标准。初看起来，这些量度标准似乎都是可取的，但实际上，用其中的大多数量度标准作贪婪处理所得到该量度意义下的最优解并不是问题的最优解，而是次优解。因此，选择能产生问题最优解的最优量度标准是使用贪婪算法的核心。 一般情况下，要选出最优量度标准并不是一件容易的事，但对某问题能选择出最优量度标准后，用贪婪算法求解则特别有效。最优解可以通过一系列局部最优的选择即贪心选择来达到，根据当前状态做出在当前看来是最好的选择，即局部最优解选择，然后再去解做出这个选择后产生的相应的子问题。每做一次贪婪选择就将所求问题简化为一个规模更小的子问题，最终可得到问题的一个整体最优解。

模式识别习题集答案解析

1、PCA和LDA的区别？ PCA是一种无监督的映射方法，LDA是一种有监督的映射方法。PCA只是将整组数据映射到最方便表示这组数据的坐标轴上，映射时没有利用任何数据部的分类信息。因此，虽然做了PCA后，整组数据在表示上更加方便（降低了维数并将信息损失降到了最低），但在分类上也许会变得更加困难；LDA在增加了分类信息之后，将输入映射到了另外一个坐标轴上，有了这样一个映射，数据之间就变得更易区分了（在低纬上就可以区分，减少了很大的运算量），它的目标是使得类别的点距离越近越好，类别间的点越远越好。 2、最大似然估计和贝叶斯方法的区别？p(x|X)是概率密度函数，X是给定的训练样本的集合，在哪种情况下，贝叶斯估计接近最大似然估计？ 最大似然估计把待估的参数看做是确定性的量，只是其取值未知。利用已知的样本结果，反推最有可能（最大概率）导致这样结果的参数值(模型已知，参数未知）。贝叶斯估计则是把待估计的参数看成是符合某种先验概率分布的随机变量。对样本进行观测的过程，把先验概率密度转化为后验概率密度，利用样本的信息修正了对参数的初始估计值。 当训练样本数量趋于无穷的时候，贝叶斯方法将接近最大似然估计。如果有非常多的训练样本，使得p(x|X)形成一个非常显著的尖峰，而先验概率p(x)又是均匀分布，此时两者的本质是相同的。 3、为什么模拟退火能够逃脱局部极小值？ 在解空间随机搜索，遇到较优解就接受，遇到较差解就按一定的概率决定是否接受，这个概率随时间的变化而降低。实际上模拟退火算法也是贪心算法，只不过它在这个基础上增加了随机因素。这个随机因素就是：以一定的概率来接受一个比单前解要差的解。通过这个随机因素使得算法有可能跳出这个局部最优解。 4、最小错误率和最小贝叶斯风险之间的关系？ 基于最小风险的贝叶斯决策就是基于最小错误率的贝叶斯决策，换言之，可以把基于最小错误率决策看做是基于最小风险决策的一个特例，基于最小风险决策本质上就是对基于最小错误率公式的加权处理。 5、SOM的主要功能是什么？怎么实现的？是winner-all-take-all 策略吗？ SOM是一种可以用于聚类的神经网络模型。 自组织映射（SOM）或自组织特征映射（SOFM）是一种使用非监督式学习来产生训练样本的输入空间的一个低维（通常是二维）离散化的表示的人工神经网络（ANN）。自组织映射与其他人工神经网络的不同之处在于它使用一个邻近函数来保持输入控件的拓扑性质。SOM网络中, 某个输出结点能对某一类模式作出特别的反应以代表该模式类, 输出层上相邻的结点能对实际模式分布中相近的模式类作出特别的反映,当某类数据模式输入时, 对某一输出结点产生最大刺激( 获胜结点) , 同时对获胜结点周围的一些结点产生较大刺激。在训练的过程中, 不断对获胜结点的连接权值作调整, 同时对获胜结点的邻域结点的连接权值作调整; 随着训练的进行, 这个邻域围不断缩小, 直到最后, 只对获胜结点进行细微的连接权值调整。 不是winner-all-take-all 策略。获胜结点产生刺激，其周围的结点也会产生一定程度的兴奋。 6、期望算法需要哪两步？请列出可能的公式并做必要的解释。 E-Step和M-Step。E-Step叫做期望化步骤，M-Step为最大化步骤。 整体算法的步骤如下所示： 1、初始化分布参数。 2、(E-Step)计算期望E，利用对隐藏变量的现有估计值，计算其最大似然估计值，以此实现期望化的过程。 3、(M-Step)最大化在E-步骤上的最大似然估计值来计算参数的值

找零问题贪心算法实现

找零问题贪心算法实现 一、实验描述 当前有面值分别为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分。 具体实现： <>T[i]; inputFile>>Coins[i]; outputFile<>TotalMoney; outputFile<<"需要找回的总钱数为: "<=TotalMoney)return true; else outputFile<<"所有硬币的总钱数是"<

return false; } return false; } int LeastCoins::changeMoney(int i,int j) { if (i>1) { if (j(T2+X-1)) m[i][j]=T2+X-1; else m[i][j]=T1+X; return m[i][j]; } } else if(i==1)// 此时 i==1 { if ((j%T[1])==0 && (j/T[1]<=Coins[1])){ m[1][j]=j/T[1]; return m[1][j]; } else return 1000000; } else return 1000000; } void LeastCoins::output()