发布时间 : 星期五 文章贪心算法详解更新完毕开始阅读8e53bfca5a8102d277a22f2b
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种动物的重量为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 卡车装载货物情况分析
从图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
Y:=A[I]; A[I]:=A[J]; A[J]:=Y; Inc(I); Dec(J); End; Until I>J;
If L
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