贪心算法详解分析

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]]

{若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.