贪心算法证明如下
贪心算法证明如下:
设定如下变量:
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]，则按贪心
方案
气瓶 现场处置方案 .pdf气瓶 现场处置方案 .doc见习基地管理方案.doc关于群访事件的化解方案建筑工地扬尘治理专项方案下载
，第I站应加油
为
T=(Way[k]-Way[I])/M-Over[I]。
若T
X[I], 则预示着，汽车开到油站K，仍然有油剩余。假设剩余W加仑汽油，则须费用Value[I]*W，如果W加仑汽油在油站K加，则须费用Value[K]*W，显然Value[K]*W
表
关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf
示在第I站的加油量会超过汽车的实际载
油量，显然是不可能的。
若T>X[I]，则表示在第I站的不加满油，而将一部分油留
待第K站加，而Value[I] 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]^.W
ay
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.
浙公网安备 33021202002483