計算機算法基礎 第2版 課件 第7章 貪心算法

1第7

章

貪心算法算法概述

2最佳郵局設置問題

3一個簡單的最佳活動安排問題

7其它最佳活動安排問題

12

兩個大禮堂的最佳活動安排問題

13

等長時間的活動的最佳安排問題

21哈夫曼編碼問題

29最佳加油計劃問題

441.算法概述

是又一個從解決小規(guī)模問題開始，逐步解決大規(guī)模問題的方法。貪心算法通常只發(fā)展一個解，而不是一組解。初始解也許是一個小規(guī)模問題的最優(yōu)解，也可能是一個大規(guī)模問題的最原始的、粗略的、不完整的、非最優(yōu)的解。貪心算法每前進一步，就把當前的解變?yōu)橐粋€稍大規(guī)模問題的最優(yōu)解，或把解變?yōu)橐粋€更好、更完整、更優(yōu)的解。算法結束時，得到一個最初大規(guī)模問題的一個最優(yōu)解，或者一個相當好的近似解。這一章所討論的例子都產生最優(yōu)的結果。23問題定義設東西方向的街上有n

戶人家，它們與街西頭的距離是：

H[1]<H[2]<H[3]<…<H[n]街上無郵局。現(xiàn)在，要建一些郵局使得任一戶人家到最近一個郵局的距離不超過100米。請設計一個O(n)的算法以確定最少需要建多少郵局，和每個郵局到街西頭的距離。解：這個題用分治法和動態(tài)規(guī)劃都不太方便。如果我們把序列H[1..n]分為兩段，那么，合并時，兩個子問題的解是不能改動的。分治法和動態(tài)規(guī)劃都不允許改動子問題的解。但是，不改動子問題的解，很難保證合并后的解是最佳的。這使得遞歸地分割和歸納地定義子問題都產生困難。(接下頁)2.最佳郵局設置問題4最佳郵局設置問題(繼續(xù)1)貪心法的思路：先確定如何走第一步，即確定第一個郵局的位置P[1]。直觀上看，為了使郵局數(shù)最小，應盡量使P[1]距街西頭遠一些。但是，因為要使得第一戶人家到它的距離不超過100米，因此，P[1]

H[1]+100。那么P[1]=H[1]+100是不是正確的決定呢？貪心法通常需要證明第一步正確，然后用歸納法證明每一步都正確，而證明中往往使用反證法。讓我們用反證法證明，有最優(yōu)解把第一個郵局設在P[1]

=H[1]+100。如果沒有，取一個最優(yōu)解。它不把第一個郵局設在P[1]，而是設在距街西頭x米處，那么必有x

<H[1]+100。讓我們來比較一下。(接下頁)5P[1]=H[1]+100H[1]

xx+100P[1]+100設在x的郵局的復蓋范圍設在P[1]的郵局的復蓋范圍最佳郵局設置問題(繼續(xù)2)由下圖可見，所有能在x處得到服務的住戶都可以在P[1]=H[1]+100處的郵局得到服務。因此把第一個郵局建在P[1]處總是正確的。這就證明了第一步是正確的。在P[1]確定后，確定P[2]的位置。這時，被P[1]復蓋的住戶可以不考慮。如果在P[1]+100米外還有人家，則可重復這一過程確定P[2]、P[3]、…。算法偽碼見下頁6Post-office(P,H,m,n) //m是郵局個數(shù)P[1]

H[1]+100 m

1 //目前為止，建了第m(=1)個郵局

for

i

2ton //貪心法逐個察看住戶位置

if

H[i]>P[m]+100 //它不在第m個郵局服務區(qū)間內

then

m

m+1 //必須再建一個新郵局 P[m]

H[i]+100

endifendforif

P[m]>H[n]

thenP[m]

H[n]

//使最后一個郵局不超過H[n]endifreturnP,m

End顯然這個算法復雜度為

O(n)。73.一個簡單的最佳活動安排問題問題定義n

個活動a1,a2,…,an

申請使用大禮堂。ai

(1

i

n)有固定的開始時間si和完成時間fi

(0

si<fi<

)。一旦ai被選中，ai在時間區(qū)間[si,fi)里獨占大禮堂。禮堂從t

=0開始可安排活動，但任何時候允許最多一個話動。

ai

和aj

稱為兼容，如果[si,fi)和[sj,fj)不相交，即要么fi

sj，要么fj

si。最佳活動安排問題：從這n

個活動中選出一個兩兩兼容的最大子集，使得盡可能多的活動在大禮堂進行。8例7.1 假定我們有以下10個活動申請使用大禮堂。i12345678910si01031376910fi24578910111314如果選出{a1,a6,a9}，它們是兼容的，但不是最優(yōu)的。最優(yōu)解可以安排4個活動。0239a1a6a91302310a1a4a10147a7一個非最優(yōu)解一個最優(yōu)解9解題思路如何選取第一個活動？選開始時間最早的活動？這個設想可立即被反例否定。選完成時間最早的活動？完全正確！定理7.1

給定n

個活動a1,a2,…,an，完成時間最早的活動一定包含在某個最優(yōu)解中。證明：設am的時間fm最早。取最優(yōu)解S。假設S含有am，證明完成。否則，設S中完成時間最早的活動為ak

am。我們有fm

≤fk。因為S中其他活動與ak兼容，他們的開始時間大于等于fk，因而也大于等于fm。所以S中其他活動與am也兼容。因此，集合S’=S

{am}–{ak}也是一個最優(yōu)解且包含am。

10算法偽碼：先按完成時間排序為F[1]

F[2]…

F[n](F[i]=fi，S[i]=si)。選a1后，與a1不兼容的不取，用同法在所余活動中選取。Greedy-Activity-Selection(S[1..n],F[1..n]，A)A

{a1} //a1是第一個中選的活動i

1

//

ai是當前為止，最后選中的一個活動for

k

2to

n

if

S[k]

F[i]

//若S[k]<

F[i]，則ak與ai不兼容

then

A

A

{ak}

i

k

//ak成為當前最后選中的活動

endifendforreturnAEnd 算法復雜度是O(n)，加上排序是O(nlgn)。11例7.1的解(圖7-4)124.其它最佳活動安排問題實踐中還有很多其它最佳活動安排問題。很多處理器的調度問題和活動安排有相同的本質。這一節(jié)再討論兩個活動安排問題。兩個大禮堂的最佳活動安排問題等長時間的活動的最佳安排問題它們在證明技巧上用了相同的方法，希望讀者能欣賞和掌握這個方法。13兩個大禮堂的最佳活動安排問題：假設有n

個活動

a1，a2，…,an申請使用大禮堂。ai(1

i

n)有一個固定的開始時間

si和固定的完成時間

fi

(0

si<fi<

)。我們有兩個禮堂，H-1和H-2，都從t=0開始可供使用。安排在同一禮堂的活動必須兩兩兼容。請設計一個O(nlgn)的貪心算法，找出最佳的活動選擇計劃使得被安排的活動數(shù)最多。(類似地，可定義

k個禮堂問題。)貪心法思路：與一個禮堂的問題相同。先把n個活動按完成時間排序，使

f1

f2

…

fn。然后從第一個活動開始，逐個檢查，并作出決定是否選取。如果選取，安排在哪個禮堂？(接下頁)14兩個大禮堂的最佳活動安排問題

(繼續(xù))具體做法：用變量Available-Time-1記錄禮堂H-1目前的可用時刻。用變量Available-Time-2記錄禮堂H-2目前的可用時刻。開始時，Available-Time-1=Available-Time-2=0。對每個活動ai(1

i

n)，逐個作出決定的規(guī)則如下：(假設Available-Time-1

Available-Time-2，否則對稱處理。)如果Available-Time-1

si，那么把ai安排在H-1，并更新Available-Time-1為

fi。如果Available-Time-2

si<Available-Time-1，那么把ai安排在H-2，并更新Available-Time-2為

fi。如果si<Available-Time-2，則丟棄不安排。(偽碼見下頁)15Two-hall-schedule(S[1..n],F[1..n],A1,A2)

//A1和A2是安排在H-1和H-2中活動的集合

Available-Time-1

Available-Time-2

0A1

A2

Sortai(1

i

n)suchthatF[1]

F[2]

…

F[n] for

i

1to

n

ifAvailable-Time-1

Available-Time-2

thenif

Available-Time-1

S[i]

then

A1

A1

{ai}

Available-Time-1

F[i]

else

if

Available-Time-2

S[i]

then

A2

A2

{ai}

Available-Time-2

F[i]

endif

endif(接下頁)

16Two-hall-schedule(繼續(xù)) elseif

Available-Time-2

S[i]

//Available-Time-1<Available-Time-2

then

A2

A2

{ai}

Available-Time-2

F[i]

else

if

Available-Time-1

S[i]

then

A1

A1

{ai}

Available-Time-1

F[i]

endif

endifendifendforEnd排序需要O(nlgn)時間。后面逐個處理活動時，每次只需O(1)時間，所以算法復雜度是O(nlgn)。下面證明它得到的解最優(yōu)。17定理7.2

對任何一個序號

i(i=1,2,…,n)，總存在一個最優(yōu)解，它對前面i個活動的處理和算法對這

i個活動的處理完全一樣。因此，存在一個和算法得到的解完全相同的最優(yōu)解。證明：我們對序號i(i=1,2,…,n)進行歸納證明。歸納基礎：當

i

=1時，算法必定把a1安排在H-1中。我們分析兩種情況：如果a1不被某最優(yōu)解M選中，假設ak

(k>1)是解M中在H-1有最小完成時間的活動。我們可用a1換走ak，解仍然最優(yōu)。如果最優(yōu)解M選中了a1但安排在H-2中，我們可以把H-1中的所有活動與H-2中的所有活動交換，解仍然最優(yōu)且a1在H-1中。因此，當

i

=1時，定理7.2正確。

歸納步驟：(接下頁)18定理7.2證明(繼續(xù)1)假設到第i步為止，有一最優(yōu)解M，它對a1到ai的處理與算法完全一樣。下面證明，存在一個最優(yōu)解，它對a1到ai+1

的處理與算法完全一樣。我們分析三種情況。(1)S[i+1]<min{Available-Time-1，Available-Time-2}這種情況，M不可能選ai+1，它必與算法一樣，拒絕ai+1。(2) Available-Time-2

S[i+1]<Available-Time-1

(對稱情況為Available-Time-1

S[i+1]<Available-Time-2)這時，解M不可能安排ai+1到H-1。如果M拒絕ai+1，而在H-2中下一個結束最早的活動是ak，k>i+1，那么，我們在M的基礎上用ai+1換走ak。因為F[i+1]

F[k]，這個交換可行。得的解含有與M一樣多的活動。所以，存在一個最優(yōu)解，它對a1到ai+1

的處理與算法完全一樣。（H-2中必有下一個活動，否則更可以安排ai+1。）(接下頁)19定理7.2證明(繼續(xù)2)(3) S[i+1]

Available-Time-1

Available-Time-2

(對稱情況為S[i+1]

Available-Time-2

Available-Time-1)這時，如解M根本不取ai+1，而在H-1中下一個結束最早的活動是ak，那么，我們用ai+1換走ak所得的解仍然最優(yōu)。如果解M取ai+1，但安排在H-2，那么如圖，解M在每個禮堂中活動可以用Available-Time-1為界分為不相交的兩個集合。所以，我們可以把Available-Time-1之后在兩個禮堂安排的所有活動互相交換。得到的解仍然最優(yōu)且ai+1在H-1中。所以，在這種情況下，也有一個最優(yōu)解，它對a1到ai+1的處理與算法完全一樣。對稱情況同理可證。歸納成功，定理7.2得證。

(圖在下頁)20結論：算法Two-hall-schedule正確解決兩個禮堂的最佳活動安排問題21等長時間的活動的最佳安排問題：有n

個活動a1，a2，…,an申請使用同一個大禮堂。時間劃分為等長的間隔

t，稱為時隙，假設

t=1小時。

slot(t)，t

=1,2,3,…表示時隙序列。每個小時只能安排一個活動或不安排活動。每個活動

ai

(1

i

n)都是申請用禮堂一個小時。每個ai有區(qū)間[si,fi]，si和fi

是正整數(shù)(si

fi)，稱為開始時隙和終止時隙。

活動ai可安排在區(qū)間中任一時隙slot(t)，t

[si,fi]。禮堂從t=1可以使用。問題：設計一個O(n2)貪心算法以安排最多的活動。

為簡單起見，假定這n個活動已按終止時隙排序，

F[1]≤F[2]≤…≤F[n]。22貪心法思路：因為F[1]≤F[2]≤…≤F[n]，序列中后面的活動有較大的終止時隙，所以當我們順序安排a1，a2，…，

an

時，盡量把活動往前面的時隙安排。具體做法是，在我們安排ai(1

i

n)時，從si

到fi，順序檢查每個時隙，一旦發(fā)現(xiàn)有某個時隙還沒有人用，則馬上把

ai安排到這個小時。我們可以證明這個思路是正確的。這里，有個復雜度的問題。如果(fi

-si)>>n，那么為ai搜索的時間是否會大于n？不會，這是因為，前面一共處理了(i-1)個活動，它們最多占用(i-1)個小時，所以我們最多需要檢查n個時隙就一定可以成功地為ai申請到一個時隙。這就保證了算法復雜度為O(n2)。(偽碼見下頁)23Max-Activities-Fixed-Length(S[1..n],F[1..n],A,T[1..n],k) //H是選中的活動集合，A是為活動安排的時隙，k=|A|A

fori

1to

n

T[i]

nil //初始化，無時隙分配給ai，記為nil fort

S[i]to(S[i]+n)

//避免F[i]過大

slot[t]

nil //所有可能被查的時隙t都初始化為空endfork

0for

i

1to

n

//順序處理活動ai t

S[i] //從S[i]開始檢查 whileslot[t]≠niland

t≤F[i] //不需擔心F[i]過大

t

t+1

endwhile(接下頁)24Max-Activities-Fixed-Length

(繼續(xù))

if

t≤F[i] //t是第一個空閑的時隙

then

A

A

{ai} //ai

被選中 slot[t]

i //時隙t被ai占了

T[i]

t

//把時隙t分配給ai k

k+1 //選中的活動數(shù)加1

endifendforreturnA,T,kEnd

算法復雜度顯然是O(n2)定理7.3

對任一序號i(i=1,2,…,n)，存在一個最優(yōu)解，它對前面i個活動的處理和我們的算法完全一樣。因此，存在一個最優(yōu)解和我們的算法得到的解完全相同。(證明見下頁)25定理7.3

證明：我們對序號i(i=1,2,…,n)進行歸納證明。歸納基礎：i

=1時，算法把

a1

安排在t=S[1]。取一最優(yōu)解M。如果M也把a1

安排在

S[1]，定理得證。否則，分析以下4種情況：解M拒絕a1，并且沒有活動被安排在S[1]。對這種情況，我們在解M的基礎上，把a1安排在S[1]。這樣會得到一個更優(yōu)的結果，與解M最優(yōu)矛盾。(B) 解M拒絕a1，并把ak（k>1）安排在S[1]。對這種情況，我們把ak

換成a1。這樣得到的解也是一個最優(yōu)解，而且把a1安排在S[1]，與算法一致，定理得證。(接下頁)26定理7.3

證明(繼續(xù)1)(C) 解M安排a1在

u>S[1]。并且，無活動安排在S[1]。對這種情況，我們把a1重新安排到t=S[1]。得到的解也是最優(yōu)解，而且把a1安排在S[1]，與我們的算法一致，定理得證。(D) 解M安排a1在u

>S[1]。并且安排ak（k>1）在S[1]。對這種情況，必有u

F[1]，和S[k]

S[1]。我們可把a1和ak對調。因為S[k]

S[1]<u

F[1]

F[k]，對調是合理的。我們得到一個最優(yōu)解把a1安排在S[1]，與我們的算法一致。所以i

=1時，定理正確。歸納步驟：假設

i=1,2,3,…,k(k

1)時，存在最優(yōu)解，它對前面i個活動的處理和算法完全一樣。現(xiàn)在證明，當i=k+1時，定理也正確。設M是在i=k時與我們算法一致的最優(yōu)解。(接下頁)27定理7.3

證明(繼續(xù)2)如果從t=S[i+1]到t=F[i+1]的每一個時隙都已被前面的活動占用，那么，最優(yōu)解M和我們的算法都必須拒絕ak+1，定理得證。所以假設w是從S[i+1]到t=F[i+1]之間第一個空閑的時隙。我們的算法把ak+1安排在

w。如果解M也把ak+1安排在

w，證明就完成了。所以，假定M沒有把ak+1安排在t=w。我們分析以下4種情況。(A)解M拒絕ak+1，并且沒有活動被安排在t=w。對這種情況，我們在M的基礎上，把ak+1安排在w。這樣會得到一個更優(yōu)的結果，與解M最優(yōu)矛盾。(B) 解M拒絕ak+1，并把活動ap（p>k+1）安排在t=w。對這種情況，在M的基礎上，把ap

換成ak+1。這樣得到的解也是一個最優(yōu)解，而且把ak+1安排在

w，與我們的算法一致。(接下頁)28定理7.3

證明(繼續(xù)3)(C）解M接收ak+1，但安排在

u>w，并且，無活動安排在

w。對這種情況，在M的基礎上，我們把ak+1重新安排到t=w。這樣得到的解與M有完全相同的活動集合，而且把ak+1安排在

w，與我們的算法一致，命題得證。(D) 解M接收ak+1但安排在u>w，并安排ap（p>k+1）在w。對這種情況，必有u

F[k+1]和S[p]

w。我們可在M的基礎上，把ak+1和ap對調。因為S[p]

w<u

F[k+1]

F[p]，所以對調是合理的。對調使我們得到另一個最優(yōu)解，它與最優(yōu)解M選取完全相同的活動集合。而且，這個最優(yōu)解把ak+1安排在w，與我們的算法一致。歸納成功。定理7.3得證。

結論：算法正確解決了等長時間的活動的最佳安排問題。29前綴碼介紹不同符號在報文中出現(xiàn)的頻率不一樣，如字母e出現(xiàn)頻率很高而z則很少出現(xiàn)。所以考慮用變長碼。用較短的碼字為頻率高的符號編碼，用較長的碼字為不常出現(xiàn)的符號編碼，會使整個文件所用比特數(shù)減少。為使接收方能正確解碼，必須是前綴碼，即任一個碼字不能是另一個碼字的前綴。反例：如字母A、B、C編為A=0，B

=1，C

=01，那么序列0101應解碼為ABAB?，ABC?，CAB?

還是CC?為了避免二義性，必須使用前綴碼。5.哈夫曼編碼問題30前綴碼與完全二叉樹的關系從一棵有

n個樹葉的完全二叉樹可構造一個n個字符的前綴碼。讓每個葉子對應一個字符。每個內結點到左右兒子的邊分別標以0和1。根到每個葉子的路徑上，每條邊上的0和1形成的序列就是該葉子對應的字符的前綴碼。這棵樹稱為前綴碼樹。這是因為，每條路徑都不是另一條的一部分。31反之，從n個字符的前綴碼，可找出對應的前綴碼樹。例：A

=01，B=001，C=000，D=110，E=10，F(xiàn)=111。如下找出對應的前綴碼樹。32

33引理7.4

假設a和b是所有字符中頻率最小的二個字符，那么存在一個最佳前綴碼樹使得它們對應的葉結點在最底層，并有共同的父結點。證明：設T是最佳前綴碼樹，高度為h，而

a對應的葉結點在第k層，k<h。如下圖所示，因為T是完全二又樹，必定有字符x,x

b，對應于一個最底層的葉子。我們有d(x)=h。如果我們把a和x在T中交換一下，會得到一個新的前綴碼樹，T’。(接下頁)34引理7.4證明(繼續(xù))我們有以下計算：B(T’)=B(T)-(kf(a)+hf(x))+(kf(x)+hf(a))=B(T)–h(f(x)-

f(a))+k(f(x)-

f(a))=B(T)-(h-k)(f(x)-

f(a))因為k<h，

f(a)≤f(x)，所以B(T’)≤B(T)。如果B(T’)<B(T)，則產生矛盾，所以有B(T’)=B(T)，說明T’也是最佳前綴碼樹，且a在底層。同理可證b也在底層?，F(xiàn)在，假設與a共一父結點的字符是y。如果b=y，那么引理得證。否則把b和x交換以使a和b共一父結點。因為a，b，y都在底層，交換不改變B(T)值，定理得證。

35哈夫曼編碼簡介貪心法的第一步：如下圖所示，貪心法的第一步是構造只有兩個葉子的樹，并讓這兩個葉子對應兩個權值(頻率)最小的字符a和b。由引理7.2知，這是正確的。ab貪心法如何繼續(xù)？研究一下a和b與他們父結點p的關系。假設T是含上面這棵小樹的字符集S的最優(yōu)前綴碼樹，由(7.1)式，我們有：(接下頁)p36

37哈夫曼編碼簡介(繼續(xù)2)由上面討論知，在貪心法走了第一步之后，下面應當構造集合S’的最佳前綴碼。然后把a和b接到它們的父親p即可。實際做法是，把a和b先接到p。把p為根的整個樹對應到一個字符p。當需要把結點p與其它結點相聯(lián)時，則把整棵樹隨著p與其它結點相聯(lián)即可。所以，貪心法每一步選兩棵權值最小的樹A和樹B相聯(lián)。它們的父親P是一個新的結點，以P為根的樹的權值是樹A和樹B的權值之和。它對應一個新符號P，其權值(頻率)是樹A和樹B的權值之和，或等價地說，是它們對應的符號A和符號B的權值(頻率)之和。一開始，n個字符對應n棵初始樹，每棵初始樹只有一個結點，沒有兒子，定義為樹葉，它的權值就是對應字符的權值(頻率)。38算法偽碼Huffman(S,f) //輸入是字符集S以及字符的頻率n

|S|Q

S

//優(yōu)先隊列Q中每個元素指向一棵初始樹。Q可用最小堆fori

1to

n-1

a

Extract-Min(Q) //取出有最小權值(頻率)的樹a

b

Extract-Min(Q) //取出第2小頻率的樹b Constructrootp //先構造含一個內結點的樹

left

(p)

treea //樹a成為p的左兒子

righ(p)

treeb //樹b成為p的右兒子

f(p)

f(a)+f(b)

//以p為根的樹的權值是樹a和樹b的權值之和

insert(Q,p) //以f(p)為關鍵字，把指向p為根的樹的指針加到Q中endforT

Extract-Min(Q) //Q中只含一棵樹End

//算法復雜度顯然是O(nlgn)。39定理7.6

哈夫曼算法Huffman(S,f)產生一個關於集合S的最佳前綴碼樹。證明：

其實，前面已討論了。我們用歸納法再正式證明一下。歸納基礎：當S只有二個字符a和b時，該算法顯然正確。歸納步驟：假設當S有n-1個字符時(n

3)，該算法正確。我們證明，當S有n個字符時，算法仍然正確。初始化后，算法其實只做一件事，就是執(zhí)行第5行起的for循環(huán)。該循環(huán)的第一輪產生一個以p為根、以樹a和樹b為子樹的二叉樹。這里，樹a和樹b對應頻率最小的兩個字符。在循環(huán)的第二輪開始時，我們觀察到以下兩點：優(yōu)先隊列Q刪去了指向樹a和樹b的指針。增加了指向p為根的樹，其權值為f(p)=f(a)+f(b)。我們可認為p為根的樹對應一個字符p，其頻率是f(p)。(接下頁)40定理7.6

證明繼續(xù)所以，for循環(huán)第二輪開始時，優(yōu)先隊列Q指向n-1個樹。這些樹對應的符號正好是集合S’=S

{p}–{a,b}中n-1個字符。而且，這n-1個樹的權值也正好是它們對應的S’中字符的權值(頻率)。由歸納假設，從循環(huán)的第2輪開始到循環(huán)完成，算法將產生一個關于S’的最佳前綴碼樹T’。由引理7.5，如果在第2輪前把結點a和b從點p切下，循環(huán)完成后再把結點a和b連接到點p就可以得到關于字符集S的最佳前綴碼樹T。顯然，我們不需要把a和b與點p切斷。哈夫曼算法確定了字符a和b之后，把整個p為根的樹對應到一個字符p，效果一樣。這就省去了切斷和再連接的操作。引入切斷和再連接的操作是為了方便證明引理7.5而已。所以，算法結束時，優(yōu)先隊列Q中只含一棵關於集合S的前綴碼樹T。由引理7.5，這個前綴碼樹T必定最佳。歸納成功，定理正確。

41例7.3 假設S={A，B，C，D

，E，F(xiàn)}。S中字符使用的頻率為f(A)=5，f(B)=8，f(C)=2，f(D)=4，f(E)=9，f(F)=12。找出它們的一組哈夫曼碼。解：424344開車從城市A到B，經過加油站，1，2，…，n。開始油箱為空，在城市A的油站(標為0號)加油后出發(fā)。城市B的加油站標為n+1號。從站(i-1)到站i距離已知為D[i]公里(1≤i

≤n+1)。定義D[0]=0。站i的油價已知為P[i]，這里的價格已轉換為元/公里。在油站n+1加的油不計入本問題，為方便，定義P[n+1]=0。汽車裝滿油可跑L公里，大于任兩相鄰加油站距離。問題：設計一個算法確定，從0號油站開始，應該在那些油站加油和加多少油使得汽車到達城市B時總共用的油錢最少。6.最佳加油計劃問題45解的基本思路從0號加油站開始，在每一個?？空荆氁卮饍蓚€問題：下一站應該停在幾號加油站？在當前停下的加油站應加多少錢的油？兩個符號：(1) R[i]表示到達i號油站時(0≤i≤n