贪心算法详解

贪心算法详解

贪心算法思想：

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

贪心算法的基本要素：

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种食品的最多拥有Wi公斤，其商品价值为Vi元/公斤，编程确定一个装货方案，使得装入卡车中的所有物品总价值最大。

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

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

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

按Vi从大到小将商品排序；

I := 1;

repeat

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

M := M - Wi;

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

else

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

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

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

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

Program Exam25;

Const Finp='Input.Txt';

Fout='Output.Txt';

Var N,M :Longint;

S :Real;

P,W :[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.

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

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

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) 统计，输出答案。

参考程序：

Program Exam26;

Const Finp='Input.Txt';

Fout='Output.Txt';

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

S :[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, ... , 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

10 100 50 30 7 34 87 100

10000

5

1 43 43 323 35 45 43 54 87 43

样例输出

171.93

508.00

贪心题目，先算出每种金属单价d， 按照d进行排序， 然后贪心地拣前面几个，直到背包满。

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以外，输入文件里每一行对应着输出文件的一行，每一行输出一个整数代表对应的订单所需的最小包裹数。

样例输入

0 0 4 0 0 1

7 5 1 0 0 0

0 0 0 0 0 0

样例输出

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的产品打开新的箱子。

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

D1=275.6 C=11.9 D2=27.4 P=2.8 N=2

Output

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。

1 若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]*W。

2 若Value[I]<Value[k]，则按贪心规则，须加油为

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

若T

若T>X[I]，则表示在第I站的不加满油，而将一部分油留待第K站加，而Value[I]<Value[k]，所以这样费用更高。

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

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机器上的加工时间分别为ai，bi。

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

输入示例：

N = 5

输出示例：

34 （最少时间）

1 5 4 2 3 （最优加工顺序）

分析：

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

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

设Mi=min{ai, bi}

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

例如：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，……，Jn}，为待加工部件的作业排序，若A机器开始加工S中的部件时，B机器还在加工其它部件，t时刻后再可利用，在这样的条件下，加工S中任务所需的最短时间T（S，t）= min{ai+T(S-{Ji},bi+max{t-ai,0})} 其中，Ji∈S。

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

假设最佳的方案中，先加工作业Ji，然后加工作业Jj，则有：

T(S,t)=ai+T(S-{Ji},bi+Max{t-ai,0})

=ai+aj+T(S-{Ji,Jj},bj+max{bi+max{t-ai,0}-aj,0})

=ai+aj+T(S-{Ji,Jj},Tij)

Tij=bj+max{bi+max{t-ai,0}-aj,0}

=bj+bi-aj+max{max{t-ai,0},aj-bi}

=bi+bj-aj+max{t-ai,aj-bi,0}

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

若将作业Ji和作业Jj的加工顺序，则有：

T’(S,t)=ai+aj+T(S-(Ji,Jj),Tji)，其中

Tji=bi+bj-ai-aj+max{t,aj,ai+aj-bj}

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

于是有：

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

即

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

算法流程如下：

for I := 1 to N do {求M数组}

if A[I] < B[I] then

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;

procedure Main;

var

I, J, Z, S, T, T1, T2: Integer;

begin

FillChar(M, Sizeof(M), 0); {求M数组的值}

for I := 1 to N do

if A[I] < B[I] then M[I] := A[I] else M[I] := B[I];

for I := 1 to N do O[I] := I;

for I := 1 to N - 1 do {从小到大排序}

for J := I + 1 to N do

if M[O[I]] > M[O[J]] then begin

Z := O[I]; O[I] :=O[J]; O[J] := Z;

end;

FillChar(Order, Sizeof(Order), 0);

S := 1; T := N;

for I := 1 to N do

if M[O[I]] = A[O[I]] then begin

{若A[O[I]]

Order[S] := O[I];

S := S + 1;

end else begin

{若B[O[I]]≧A[O[I]]，则插在加工序列的后面}

Order[T] := O[I];

T := T - 1;

end;

{计算最少加工时间}

T1 := 0; T2 := 0;

for I := 1 to N do begin

T1 := T1 + A[Order[I]];

if T2 < T1 then T2 := T1;

T2 := T2 + B[Order[I]];

end;

Min := T2;

end;

procedure Out; {打印输出}

var I: Integer;

begin

Assign(Output, Outp); Rewrite(Output);

Writeln(Min); {输出最少时间}

for I := 1 to N do {输出最佳加工序列}

Write(Order[I], ' ');

Writeln;

Close(Output);

end;

Begin

Init; {输入}

Main; {主过程}

Out; {输出}

End.

本文来源：https://www.2haoxitong.net/k/doc/8e53bfca5a8102d277a22f2b.html