資源簡(jiǎn)介

貪心算法
在實(shí)際生活中，經(jīng)常需要求一個(gè)問(wèn)題的可行解和最優(yōu)解，這就是所謂的最優(yōu)化問(wèn)題。每
個(gè)最優(yōu)化問(wèn)題都包含一組限制條件和一個(gè)優(yōu)化函數(shù)，符合限制條件的問(wèn)題求解方案稱(chēng)為可行
解，使優(yōu)化函數(shù)取得最佳值的可行解稱(chēng)為最優(yōu)解。
貪心法是求解這類(lèi)問(wèn)題的一種常用算法，它是從問(wèn)題的某一個(gè)初始解出發(fā)，采用逐步構(gòu)
造最優(yōu)解的方法向給定的目標(biāo)前進(jìn)。在每個(gè)局部階段，都做出一個(gè)看上去最優(yōu)的決策（即某
種意義下的、或某個(gè)標(biāo)準(zhǔn)下的局部最優(yōu)解），并期望通過(guò)每次所做的局部最優(yōu)選擇產(chǎn)生出一
個(gè)全局最優(yōu)解。但采用貪心法求解不能保證對(duì)所有問(wèn)題都能得到最優(yōu)解，這時(shí)我們可以選擇
其它解決最優(yōu)化問(wèn)題的算法，如動(dòng)態(tài)規(guī)劃等。
做出貪心決策的依據(jù)稱(chēng)為貪心準(zhǔn)則（策略），注意決策一旦做出，就不可再更改。貪心
與遞推不同的是，推進(jìn)的每一步不是依據(jù)某一固定的遞推式，而是做一個(gè)當(dāng)時(shí)看似最佳的貪
心選擇（操作），不斷地將問(wèn)題實(shí)例歸納為更小的相似子問(wèn)題。所以，歸納、分析、選擇正
確合適的貪心準(zhǔn)則，是正確解決貪心問(wèn)題的關(guān)鍵。下面我們先看兩個(gè)簡(jiǎn)單而典型的例子。
例 1、刪數(shù)問(wèn)題
[問(wèn)題描述] 鍵盤(pán)輸入一個(gè)高精度的正整數(shù) n(≤240 位)，去掉其中任意 s個(gè)數(shù)字后剩下
的數(shù)字按原左右次序?qū)⒔M成一個(gè)新的正整數(shù)。編程對(duì)給定的 n 和 s，尋找一種方案，使得剩
下的數(shù)字組成的新數(shù)最小。
[輸入格式] n
s
[輸出格式] 最后剩下的最小數(shù)。
[樣例輸入] 178543
4
[樣例輸出] 13
[算法分析]
由于正整數(shù) n 的有效數(shù)位為 240 位，所以很自然地采用字符串類(lèi)型存貯 n。那么如何決
定哪 s位被刪除呢？是不是最大的 s個(gè)數(shù)字呢？顯然不是，大家很容易舉出一些反例。為了
盡可能逼近目標(biāo)，我們選取的貪心策略為：每一步總是選擇一個(gè)使剩下的數(shù)最小的數(shù)字刪去，
即按高位到低位的順序搜索，若各位數(shù)字遞增，則刪除最后一個(gè)數(shù)字；否則刪除第一個(gè)遞減
區(qū)間的首字符，這樣刪一位便形成了一個(gè)新數(shù)字串。然后回到串首，按上述規(guī)則再刪下一個(gè)
數(shù)字。重復(fù)以上過(guò)程 s次為止，剩下的數(shù)字串便是問(wèn)題的解了。
例如：n=178543
s=4
刪數(shù)的過(guò)程如下：
n=178543 {刪掉 8}
17543 {刪掉 7}
1543 {刪掉 5}
127
143 {刪掉 4}
13 {解為 13}
這樣，刪數(shù)問(wèn)題就與如何尋找遞減區(qū)間首字符這樣一個(gè)簡(jiǎn)單的問(wèn)題對(duì)應(yīng)起來(lái)。不過(guò)還要
注意一個(gè)細(xì)節(jié)性的問(wèn)題，就是可能會(huì)出現(xiàn)字符串串首有若干 0的情況，甚至整個(gè)字符串都是
0的情況。按以上貪心策略編制的程序框架如下：
輸入 n，s；
while s>0 do
begin
i：=1； {從串首開(kāi)始找}
while (idelete (n，i，1)； {刪除字符串 n的第 i個(gè)字符}
s:=s-1；
end；
while (length(n)>1)and (n[1]=‘0’) do delete(n，1，1)；
{刪去串首可能產(chǎn)生的無(wú)用零}
輸出 n；
例 2、取數(shù)游戲
[問(wèn)題描述] 給出 2*n(n<=100)個(gè)自然數(shù)（數(shù)小于等于 30000）。游戲雙方分別為 A方（計(jì)
算機(jī)方）和 B方（對(duì)奕的人）。只允許從數(shù)列兩頭取數(shù)。A先取，然后雙方依次輪流取數(shù)。取
完時(shí)，誰(shuí)取得的數(shù)字總和最大為取勝方；雙方和相等，屬于 A勝。試問(wèn) A方可否有必勝的策
略？
[輸入格式] 鍵盤(pán)輸入 n及 2*n 個(gè)自然數(shù)。
[輸出格式] 共 3*n+2 行，其中前 3*n 行為游戲經(jīng)過(guò)。每 3 行分別為 A 方所取的數(shù)和 B
方所取的數(shù)，及 B方取數(shù)前應(yīng)給予的適當(dāng)提示，讓游戲者選擇取哪一頭的數(shù)（L/R—左端或右
端）。最后 2行分別為 A方取得的數(shù)和和 B方取得的數(shù)和。
[算法分析]
設(shè) n=4，自然數(shù)列為:7 9 3 6 4 2 5 3，我們?cè)O(shè)計(jì)一種原始的貪心策略，讓 A每
次取數(shù)列兩頭較大的那個(gè)數(shù)，則游戲者也不會(huì)傻，他也會(huì)這么干，所以在上面的數(shù)列中，A
方會(huì)順序取 7、3、4、5，B方會(huì)順序取 9、6、2、3，由此得出：A方取得的數(shù)和為 7+3+4+5=19，
B方取得的數(shù)和為 9+6+2+3=20，按照規(guī)則，判定 A方輸。
其實(shí)，如果按上述貪心策略去游戲，成敗取決于給你的測(cè)試數(shù)據(jù)！不過(guò)，雖然 A方敗給
B方，但是我們卻發(fā)現(xiàn)了一個(gè)有趣的事實(shí)：A方取走偶位置的數(shù)后，剩下兩端數(shù)都處于奇位置；
反之，若 A 方取走奇位置的數(shù)后，剩下兩端數(shù)都處于偶位置。即無(wú)論 B 方如何取法，A 方即
可以取走奇位置的所有數(shù)，亦可以取走偶位置的所有數(shù)。由此萌發(fā)出另一種有效的貪心策略：
若能夠讓 A方取走“數(shù)和較大的奇（或偶）位置上的所有數(shù)”，則 A方必勝。這樣，取數(shù)問(wèn)題
便對(duì)應(yīng)于一個(gè)簡(jiǎn)單問(wèn)題：讓 A方取奇偶位置中數(shù)和較大的一半數(shù)。設(shè) j為 A取數(shù)的奇偶位置
標(biāo)志，則 j=0 表示偶位置數(shù)和較大，A取偶位置上的所有數(shù)；j=1 表示奇位置數(shù)和較大，A取
奇位置的所有數(shù)。
128
設(shè) SA，SB 分別表示 A方取數(shù)和，B方取數(shù)和（SA≥SB）；a存儲(chǔ) 2*n 個(gè)自然數(shù)序列；lp，
rp 為序列的左端位置和右端位置；ch為 B方取數(shù)的位置信息（’L’或’R’）；按上述貪心思
想編寫(xiě)的程序框架如下：
讀入 n及 a；
SA：=0；SB：=0； {計(jì)算 A方取數(shù)和、B方取數(shù)和，A方取數(shù)的位置標(biāo)志}
for i：=1 to n do
begin
SA：=SA+a[2*i-1]；SB：=SB+a[2*i]；
end；
if SA>=SB then j:=1
else begin j:=0；交換 SA 和 SB；end；
lp：=1；rp：=2*n；
for i：=1 to n do {A 方和 B方依次進(jìn)行 n次對(duì)奕}
begin
if ((j=1) and (lp mod 2=1)) or ((j=0)and (lp mod 2=0)) {若 A方應(yīng)取奇位
置數(shù)且左端位置為奇，或者 A方應(yīng)取偶位置數(shù)且左端位置為偶，則 A方取走左端位置的數(shù)}
then begin writeln(a[lp])；lp：=lp+1；end {輸出}
else begin writeln(a[rp])；rp：=rp-1；end；
write(‘ B=L/R ’)；{提示信息}
repeat {B 方取數(shù)，輸入 L或 R}
readln(ch)；
if ch=‘L’ then begin write(a[lp])；lp：=lp+1；end； {輸出}
if ch=‘R’ then begin writeln(a[rp])；rp：=rp-1；end；
until （ch=‘L’） or (ch=‘R’)；
end；
輸出 A 方取數(shù)的和 SA 和 B 方取數(shù)的和 SB；
小結(jié)：
以上兩個(gè)例題所用的貪心思想還是很明顯的，選取的貪心策略也很直觀（可能也是唯
一的）；不僅能得到最優(yōu)解，而且解的正確性也可以得到嚴(yán)格的證明。但有些問(wèn)題采用貪心法
求解時(shí)，貪心策略可能有多種，在針對(duì)性不同的測(cè)試數(shù)據(jù)下，帶來(lái)的效果可能也不一樣，并
不是總能得到最優(yōu)解，而且解的正確性證明也很困難。最典型的例子就是 0/1 背包問(wèn)題。
例3、0/1背包問(wèn)題
[問(wèn)題描述] 有一容量為weight的背包?，F(xiàn)在要從n件物品中選取若干裝入背包中，每件
物品i的重量為w[i]，價(jià)值為p[i]。定義一種可行的背包裝載為：背包中物品的總重量不能超
過(guò)背包的容量，并且一個(gè)物品要么全部選取，要么不選取。定義最佳裝載是指所裝入的物品
價(jià)值最高，并且是可行的背包裝載。
[樣例輸入]
11 {weight}
129
4 {n}
2 4 6 7 {w[i]}
6 10 12 13 {p[i]}
[樣例輸出]
0 1 0 1
23
[問(wèn)題分析]
設(shè)數(shù)組choice[1..n]，若choice[i]=1表示物品i裝入背包中，choice[i]=0表示物品i不
裝入背包中。則choice=[0，1，0，1]是一種可行的背包裝載方案，也是一種最佳裝載方案，
此時(shí)總價(jià)值為23。
0/1 背包問(wèn)題有好幾種貪心準(zhǔn)則，每種貪心準(zhǔn)則都是采用多步過(guò)程來(lái)完成背包的裝入，
在每一步過(guò)程中利用某種固定的貪心準(zhǔn)則選擇一個(gè)物品裝入背包。
一種貪心準(zhǔn)則為：從剩余的物品中，選出可以裝入背包的價(jià)值最大的物品，利用這種規(guī)
則，價(jià)值最大的物品首先被裝入（假設(shè)有足夠容量），然后是下一個(gè)價(jià)值最大的物品，如此
繼續(xù)下去。這種貪心準(zhǔn)則不能保證得到最優(yōu)解。例如 weight=105，n=3，w=[100，10，10]，
p=[20，15，15]。按照以上這種“價(jià)值貪心準(zhǔn)則”，獲得的解為 choice=[1，0，0]，這種方
案的總價(jià)值為 20。而最優(yōu)解為 choice =[0，1，1]，其總價(jià)值為 30。
另一種方案是“重量貪心準(zhǔn)則”，即從剩下的物品中選擇可裝入背包的重量最小的物品。
雖然這種規(guī)則對(duì)于前面的例子能產(chǎn)生最優(yōu)解，但在一般情況下不一定能得到最優(yōu)解，例如
weight=25，n=2，w=[10，20]，p=[5，100]。獲得的解為choice=[1，0]，總價(jià)值為5，比最
優(yōu)解choice =[0，1]的總價(jià)值100要差。
本題的另一方案為“單位價(jià)值貪心準(zhǔn)則”，這種方案是從剩余物品中選擇可裝入包的p[i]
/w[i]值最大的物品，這種策略也不能保證得到最優(yōu)解。例如weight=30，n=3，w=[20，15，
15]，p=[40，25，25]。獲得的解為choice=[1，0，0]，總價(jià)值為40。而最優(yōu)解為choice=[0，
1，1]的總價(jià)值為50。
既然任何一種貪心策略都不能保證得到最優(yōu)解，那么本題是不是不應(yīng)該用貪心法？其實(shí)
我們不必因所考察的幾個(gè)貪心策略都不能保證得到最優(yōu)解而沮喪（或放棄），因?yàn)?0/1 背包
問(wèn)題是一個(gè)復(fù)雜的 NP問(wèn)題。對(duì)于這類(lèi)問(wèn)題，也許根本就不可能找到具有多項(xiàng)式時(shí)間的算法。
雖然按“單位價(jià)值貪心準(zhǔn)則”遞減的次序裝入物品不能保證得到最優(yōu)解，但它是一個(gè)直覺(jué)上
近似的解，而且時(shí)間復(fù)雜度僅為 O(nlogn)。造成多種貪心都不能全對(duì)的原因其實(shí)在于，在很
多情況下，無(wú)法將背包填滿(mǎn)，空間上的浪費(fèi)間接降低了實(shí)際上的單位價(jià)值。當(dāng)然本題很有一
種思路，就是用動(dòng)態(tài)規(guī)劃求解。
小結(jié)：
與這個(gè)題目類(lèi)似的問(wèn)題很多，比如部分背包問(wèn)題、船的最優(yōu)裝載問(wèn)題、硬幣的最少組合
問(wèn)題、多機(jī)調(diào)度問(wèn)題等。留給大家回去思考：哪些可以用貪心法、哪些不可以。
例 4、活動(dòng)選擇
130
[問(wèn)題描述] 假設(shè)有一個(gè)需要使用某一資源的 n個(gè)活動(dòng)組成的集合 S，S={1，……，n}。
該資源一次只能被一個(gè)活動(dòng)所占用，每一個(gè)活動(dòng)有一個(gè)開(kāi)始時(shí)間 bi和結(jié)束時(shí)間 ei (bi≤ei)。
若 bi≥ej或者 bj≥ei，則活動(dòng) i和活動(dòng) j兼容。
你的任務(wù)是:選擇由互相兼容的活動(dòng)組成的最大集合。
[輸入格式] 輸入文件名為：act.in，共 n+1 行，其中第 1行為 n，第 2行到第 n+1 行表
示 n個(gè)活動(dòng)的開(kāi)始時(shí)間和結(jié)束時(shí)間（中間用空格隔開(kāi)），格式為：
n
b1 e1
………
bn en
[輸出格式] 輸出文件名為：act.out，共兩行，第 1行為滿(mǎn)足要求的活動(dòng)占用的時(shí)間 t，
第 2行為最大集合中的活動(dòng)序號(hào)，每個(gè)數(shù)據(jù)之間用一個(gè)空格隔開(kāi)。
[樣例輸入]
11
3 5
1 4
12 14
8 12
0 6
8 11
6 10
5 7
3 8
5 9
2 13
[樣例輸出]
14
2 3 6 8
[算法分析]
我們使用的貪心策略如下，即每一步總是選擇這樣一個(gè)活動(dòng)來(lái)占用資源：它能夠使得余
下的未調(diào)度時(shí)間最大化，使得兼容的活動(dòng)盡可能多。為了達(dá)到這個(gè)目的，我們將 n個(gè)待選活
動(dòng)按結(jié)束時(shí)間遞增的順序排列：e1’≤e2’≤……≤en’。
首先將遞增序列中的活動(dòng)1進(jìn)入集合S。然后依次分析遞增序列中的活動(dòng)2，活動(dòng)3，……，
活動(dòng) n，每次將與 S中的活動(dòng)兼容的活動(dòng)加入到集合 S中。
我們結(jié)合問(wèn)題的樣例輸入，先將 11 個(gè)活動(dòng)的活動(dòng)號(hào)、開(kāi)始時(shí)間、結(jié)束時(shí)間及遞增編號(hào)
列表（表 1）如下：
表 1
活動(dòng)序號(hào) i 開(kāi)始時(shí)間 b[i] 結(jié)束時(shí)間 e[i] 按活動(dòng)結(jié)束時(shí)間遞增的序號(hào) j
131
1 3 5 2
2 1 4 1
3 12 14 11
4 8 12 9
5 0 6 3
6 8 11 8
7 6 10 7
8 5 7 4
9 3 8 5
10 5 9 6
11 2 13 10
按照以上這種貪心策略，貪心選擇的過(guò)程如下：
時(shí)間 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
選擇活動(dòng) |—|—|—|—|—|—|—|—|—|—|—|—|—|—|
2 —————活動(dòng) 2兼容（持續(xù)時(shí)間 1-4），加入 S，S={2}，t=4
1 不兼容，放棄
5 不兼容，放棄
8 ————活動(dòng) 8兼容（持續(xù)時(shí)間 5-7），加入 S，S={2，8}，t=7
9 不兼容，放棄
10 不兼容，放棄
7 不兼容，放棄
6 —————活動(dòng) 6兼容（持續(xù)時(shí)間 8-11），加入 S,
S={2，8，6}，t=11
4 不兼容，放棄
11 不兼容，放棄
3 ———活動(dòng) 3兼容（持續(xù)時(shí)間 12-14），
加入 S，S={2，8，6，3}，t=14
所以，問(wèn)題的解為：t=14，S={2，8，6，3}。根據(jù)以上算法編寫(xiě)的程序框架如下：
S：={1}；j：=1； {遞增序列中的活動(dòng) 1進(jìn)入集合 S，設(shè)定最近進(jìn)入 S的活動(dòng)序號(hào)為 1}
for i：=2 to n do
if bi’>=ej’ {若遞增序列中的活動(dòng) i與 S集合中的活動(dòng)兼容}
then begin
S：=S+{i}； {活動(dòng) i進(jìn)入集合 S}
t：=ei’； {計(jì)算占用時(shí)間}
j：=i； {設(shè)定最近進(jìn)入 S的活動(dòng)序號(hào)為 i}
end；
輸出占用時(shí)間 t；
for i：=1 to n do
132
if i in S then 輸出活動(dòng) i的序號(hào)；
小結(jié)：
一、 貪心算法的基本要素及與動(dòng)態(tài)規(guī)劃算法的關(guān)系
對(duì)于一個(gè)具體的問(wèn)題，怎么知道是否可以用貪心算法求解呢？得到的解是不是問(wèn)題的最
優(yōu)解呢？這個(gè)問(wèn)題很難給予肯定的回答。但是一般來(lái)說(shuō)這類(lèi)問(wèn)題具有兩個(gè)重要的性質(zhì)：
1、 貪心選擇性質(zhì)：即問(wèn)題的整體最優(yōu)解可以通過(guò)一系列局部最優(yōu)的貪心選擇達(dá)到。
這是貪心法可行的第一個(gè)基本要素，也是貪心算法與動(dòng)態(tài)規(guī)劃算法的主要區(qū)別。
在動(dòng)態(tài)規(guī)劃算法中，每步所做出的選擇往往依賴(lài)于相關(guān)子問(wèn)題的解。因而只有
解出相關(guān)子問(wèn)題后，才能做出選擇。而貪心算法是先做出當(dāng)前的局部最優(yōu)選擇，
然后再去解這個(gè)選擇后產(chǎn)生的相應(yīng)子問(wèn)題。所以，貪心算法可以依賴(lài)以往所做
的選擇，但決不依賴(lài)將來(lái)所做的選擇，也不依賴(lài)子問(wèn)題的解。
對(duì)于一個(gè)具體問(wèn)題，我們一般通過(guò)數(shù)學(xué)歸納法證明他是否具有貪心選擇性
質(zhì)。但在實(shí)際比賽中，由于時(shí)間等因素，一般不會(huì)嚴(yán)格地證明，而是要把問(wèn)題
的各個(gè)方面、各種情況考慮清楚，多找數(shù)據(jù)測(cè)試和驗(yàn)證。
2、 最優(yōu)子結(jié)構(gòu)性質(zhì)：當(dāng)一個(gè)問(wèn)題的最優(yōu)解包含其子問(wèn)題的最優(yōu)解時(shí)，稱(chēng)此問(wèn)題具
有最優(yōu)子結(jié)構(gòu)性質(zhì)。這一性質(zhì)是決定一個(gè)問(wèn)題可否采用貪心或動(dòng)態(tài)規(guī)劃算法的
關(guān)鍵特性。比如，在例 4 的活動(dòng)安排中，其最優(yōu)子結(jié)構(gòu)性質(zhì)表現(xiàn)為：若 S 是關(guān)
于 E 的活動(dòng)安排問(wèn)題的包含活動(dòng) 1 的一個(gè)最優(yōu)解，則相容活動(dòng)集合 S’=S-{1}
是關(guān)于 E’={i 屬于 E : bi>=e1}的活動(dòng)安排問(wèn)題的一個(gè)最優(yōu)解。
雖然貪心算法和動(dòng)態(tài)規(guī)劃算法都要求問(wèn)題具有最優(yōu)子結(jié)構(gòu)性質(zhì)，但兩者不是通用的。比
如前面講到的 0/1 背包問(wèn)題和部分背包問(wèn)題，都具有最優(yōu)子結(jié)構(gòu)性質(zhì)，但前者不可以用貪心，
而只能用動(dòng)態(tài)規(guī)劃，本質(zhì)原因是：存在空間上的浪費(fèi)；而后者是是可以用貪心求的最優(yōu)解。
另外，一般而言貪心算法的效率比動(dòng)態(tài)規(guī)劃要高。
二、 思考樹(shù)和圖論中的哪些算法是采用的貪心思想。
哈夫曼編碼問(wèn)題、Dijkstra 算法求解單源最短路徑問(wèn)題、Prim 算法和 Kruskal 算法求
解最小生成樹(shù)問(wèn)題。
例 5、雇傭計(jì)劃
[問(wèn)題描述] 一位管理項(xiàng)目的經(jīng)理想要確定每個(gè)月需要的工人，他當(dāng)然知道每月所需的
最少工人數(shù)。當(dāng)他雇傭或解雇一個(gè)工人時(shí)，會(huì)有一些額外支出。一旦一個(gè)工人被雇傭，即使
他不工作，他也將得到工資。這位經(jīng)理知道雇傭一個(gè)工人的費(fèi)用，解雇一個(gè)工人的費(fèi)用和一
個(gè)工人的工資。現(xiàn)他在考慮一個(gè)問(wèn)題：為了把項(xiàng)目的費(fèi)用控制在最低，他將每月雇傭或解雇
多少個(gè)工人。
[輸入格式] 輸入文件含有三行。第一行為月數(shù) n（不超過(guò) 12）。第二行含雇傭一個(gè)工人
的費(fèi)用，一個(gè)工人的工資和解雇一個(gè)工人的費(fèi)用（≤100）。第三行含 n個(gè)數(shù)，分別表示每月
最少需要的工人數(shù)（≤1000）。每個(gè)數(shù)據(jù)之間有一個(gè)空格隔開(kāi)。
[輸出格式] 輸出僅一行，表示項(xiàng)目的最小總費(fèi)用。
[輸入樣例]
133
3
4 5 6
10 9 11
[輸出樣例]
199
[算法分析]
我們從第一個(gè)月開(kāi)始，逐月計(jì)算現(xiàn)有工人數(shù)，先給這些工人發(fā)放工資。如果雇傭了新工
人，則必須給新上崗人員發(fā)放雇傭費(fèi)用；如果削減了部分工人，則必須給下崗人員發(fā)放解雇
費(fèi)用。當(dāng)月發(fā)放的工資+雇傭（或解雇）費(fèi)用構(gòu)成了一個(gè)月的總費(fèi)用。我們從第一個(gè)月開(kāi)始，
逐月累計(jì)項(xiàng)目總費(fèi)用，直至計(jì)算出 n個(gè)月的總費(fèi)用為止。問(wèn)題是怎樣將這筆費(fèi)用控制在最低？
設(shè) mincost 表示最小費(fèi)用和，初始時(shí) mincost=0；now 表示現(xiàn)有工人數(shù)，初始時(shí) now=0；min[i]
表示第 i個(gè)月所需要的最少工人數(shù)（1≤i≤n）；n表示月數(shù)；f表示解雇費(fèi)用；s表示工資；
h表示雇傭費(fèi)用。則我們需要解決下面的兩個(gè)問(wèn)題：
1、怎樣在當(dāng)月工人數(shù)不足的情況下確定雇傭方案
如果第 i個(gè)月的所需最少人數(shù) min[i]大于現(xiàn)有工人數(shù) now，則需要雇傭工人。為了盡可
能少地減少雇傭費(fèi)用，我們不妨雇傭(min[i]-now)個(gè)工人，使得第 i 個(gè)月的工人數(shù)正好為
min[i]；如果 min[i]=now，則維持現(xiàn)有工人數(shù) now 不變。算法思想如下：
if min[i]>now
then begin
mincost：=mincost+h*(min[i]-now)；now：=min[i]；
end；
mincost：=mincost+now*s； { 顯然，這樣的雇傭費(fèi)用支出是最節(jié)約的 }
2、怎樣在當(dāng)月工人數(shù)多余的情況下確定解雇方案
如果現(xiàn)有工人數(shù) now 大于第 i個(gè)月最少需要的工人數(shù) min[i]，則需要解雇一部分工人，
最佳方案是否一定是解雇(now-min[i])個(gè)工人呢？不是的。例如對(duì)于示例中的數(shù)據(jù)，依上述
方法計(jì)算：
第 1個(gè)月雇傭 10人：mincost=mincost+h*(min[i]-now)+s*min[i]
=0+4*10+5*10
=90 now=10
第 2個(gè)月解雇 1人，使得現(xiàn)有工人數(shù)為 9人：
mincost=mincost+f*(now-min[2])+d*min[2]
=90+6*1+9*5
=141 now=9
第 3個(gè)月雇傭 2人，使得現(xiàn)有工人數(shù)為 11人：
mincost=mincost+h*(min[3]-now)+d*min[3]
=141+4*2+5*11
=204 now=11
134
顯然，該雇傭計(jì)劃的總費(fèi)用（204）并不是最少的，因?yàn)槿绻?2 個(gè)月不解雇 1 人，仍
維持 10人，第 3個(gè)月再雇傭 1人，這種情況下的總費(fèi)用為（4*10+5*10）+（5*10）+（4*1+5*11）
=90+50+59=199，即為樣例輸出。由此看出，解雇的人數(shù)應(yīng)比(now-min[i])少一些，那么少多
少呢？我們采取這樣的貪心策略去確定：盡可能少地解雇工人，并且在工資支出合理的前提
下盡可能使現(xiàn)有工人數(shù)維持在一個(gè)最長(zhǎng)時(shí)間內(nèi)，以減少雇傭和解雇的額外支出。
實(shí)現(xiàn)的方法是：在 min[i]～min[n]間按最少需要人數(shù)遞增的順序，將月份排成序列 y1 ，
y2，……，yn-i，yn-i+1(其中 i≤yj≤n，1≤j≤n-i+1，如圖 1)。從第 yj個(gè)月出發(fā)按照最少需要
遞減的順序檢查 min[yj]、min[yj-1]，……，一旦發(fā)現(xiàn)第 yj月超員，且這些工人在第 yj+1個(gè)月
雇傭與第 i 到第 yj 月期間解雇的總費(fèi)用，比第 i 到第 yj 個(gè)月連續(xù)使用的費(fèi)用節(jié)約，即
（min[yj]n)))，則
在第 i個(gè)月解雇 now-min[yj]個(gè)工人，使現(xiàn)有工人數(shù)變?yōu)?min[yj]；否則維持現(xiàn)有工人數(shù)不變。
圖 1
算法思想如下：
在 min[i]～min[n]間按最少需要人數(shù)遞增的順序，將月份排成 y1，……，yn-i+1；
for j:=n-i downto 1 do
if (min[yj]then begin
mincost：=mincost+f*(now-min[yj])；now：=min[yj]；
and
mincost：=mincost+s*now；
我們從 i=1 開(kāi)始，依上述辦法逐月累計(jì)費(fèi)用總和，直至 i=n 為止。此時(shí)的費(fèi)用總和最少。
例如對(duì)于示例中的數(shù)據(jù)，依上述方法計(jì)算：
第 1個(gè)月雇傭 10人，費(fèi)用總和為 90；
第 2個(gè)月維持現(xiàn)有人數(shù)不變，費(fèi)用總和為 90+5*10=140；
第 3個(gè)月雇傭 1人，工人數(shù)增至 11，費(fèi)用總和為 140+5*11-14=199。
顯然，這個(gè)答案與樣本輸出一致。結(jié)合上述分析得出本題總的算法框架如下：
mincost：=0；now：=0； {初始化}
for i：=1 to n do
begin
if min[i]>now
135
then 在現(xiàn)有人數(shù)不足情況下確定第i個(gè)月的雇傭方案并累計(jì)最小費(fèi)用mincost；
else 在現(xiàn)有人數(shù)多余情況下確定第i個(gè)月的解雇方案并累計(jì)最小費(fèi)用mincost；
end；
輸出項(xiàng)目的最小費(fèi)用 mincost；
例 6、自動(dòng)柜員機(jī) ATM
[問(wèn)題描述]
在一個(gè)銀行的大廳里有 100 個(gè)自動(dòng)柜員機(jī)，編號(hào)分別為 0..99，每個(gè)會(huì)員顧客都能通過(guò)
30
這些柜員機(jī)提取<=10 ducats（一種早期的流通硬幣單位）的借款業(yè)務(wù)，但必須在一個(gè)星期
內(nèi)還是通過(guò)這些柜員機(jī)完成還款業(yè)務(wù)。這種柜員機(jī)很特別，每個(gè)柜員機(jī)只能完成一種簡(jiǎn)單的
i
動(dòng)作：供客戶(hù)提取固定數(shù)目的現(xiàn)金或接受客戶(hù)固定數(shù)目的還款。第 i 個(gè)柜員機(jī)只能提供 2
i
ducats 的借款業(yè)務(wù)，如果 i是偶數(shù)的話(huà)；而如果 i是奇數(shù)的話(huà)，則第 i個(gè)柜員機(jī)只能提供 2
ducats 的還款業(yè)務(wù)。
現(xiàn)在，如果有一個(gè)客戶(hù)想要用這些柜員機(jī)借一定數(shù)目的錢(qián)，但是每個(gè)柜員機(jī)都只能使用
一次，那么，他該使用哪些柜員機(jī)呢？
一個(gè)星期內(nèi)還款時(shí)，他又該使用哪些柜員機(jī)呢？
比如，他要借7 ducats，則他會(huì)從4號(hào)柜員機(jī)拿到16 ducats，從0號(hào)柜員機(jī)拿到1 ducats，
再到 3號(hào)柜員機(jī)還掉 8 ducats，到 1號(hào)柜員機(jī)還掉 2 ducats。
一個(gè)星期內(nèi)還款時(shí)，他會(huì)到 3號(hào)柜員機(jī)先還掉 8 ducats，再到 0號(hào)柜員機(jī)拿到 1 ducats。
請(qǐng)你編寫(xiě)一個(gè)程序，當(dāng)一個(gè)客戶(hù)借款，告訴他該使用哪些柜員機(jī)，以后還款時(shí)又該使用
哪些柜員機(jī)。
[輸入]
輸入文件 ban.in，第一行為整數(shù) N（N<=1000），表示客戶(hù)的數(shù)目。下面有 N行，每行為
30
一個(gè)整數(shù)，表示每個(gè)客戶(hù)要借多少錢(qián)。注意：每個(gè)客戶(hù)最多能借 10 ducats。
[輸出]
輸出文件 ban.out，共 2N行，第 2i-1 行表示客戶(hù) i借款時(shí)該使用哪些柜員機(jī)，第 2i行
表示客戶(hù) i還款時(shí)該使用哪些柜員機(jī)（1<=i<=N），每行都要求按柜員機(jī)編號(hào)從大到小輸出，
每個(gè)編號(hào)之間用 1個(gè)空格隔開(kāi)。
如果業(yè)務(wù)無(wú)法成交，則輸出 NIE。
[樣例]
ban.in
2
7
633825300114114700748351602698
ban.out
4 3 1 0
3 0
NIE
99 3 1
136
[問(wèn)題分析] 貪心，時(shí)間和空間復(fù)雜度都是 O(n)。題目中說(shuō)如果 odd(i)則付出，否則得
到硬幣，這很容易讓我們想到-2進(jìn)制。
例 7、獨(dú)木舟 （KAJ）
[問(wèn)題描述]
我們計(jì)劃組織一個(gè)獨(dú)木舟旅行。租用的獨(dú)木舟都是一樣的，最多乘兩人，而且載重有一
個(gè)限度?，F(xiàn)在要節(jié)約費(fèi)用，所以要盡可能地租用最少的舟。
[任務(wù)] 讀入載重量，參加旅行的人數(shù)以及每個(gè)人的體重。計(jì)算所需要租船數(shù)目。
[輸入] 文件 KAJ.IN 的第一行是 w, 80<=w<=200,每條船最大的載重量。
第二行是整數(shù) n, 1 <= n <= 30000,參加旅行的人數(shù)。
接下來(lái)的 n行，每行是一個(gè)整數(shù)，范圍[5..w]。表示每個(gè)人的重量。
[輸出] 最小租用數(shù)目。
[樣例輸入與輸出]
KAN.IN:
100
9
90
20
20
30
50
60
70
80
90
KAJ.OUT:
6
[問(wèn)題分析] 貪心，找到一個(gè)重量最大的，讓它盡可能與重量大的人同乘一船。如此循環(huán)
直至所有人都分配完畢。時(shí)間：O（N），空間 O（W）。
137回溯法
在程序設(shè)
優(yōu)解,例
題、騎土巡游問(wèn)題、迷宮問(wèn)題、數(shù)的拆分、全排列問(wèn)題、冪集和子集問(wèn)題
雖然是按照
定的規(guī)則完成一些任務(wù)
這些任務(wù)和規(guī)則是無(wú)法用精確的數(shù)學(xué)公式來(lái)描述的
不能根據(jù)
某種確定的計(jì)算法則去生成解,而是需要采用試探和回溯的搜索策略去求解。因此,回溯法是程序
設(shè)計(jì)中解決這類(lèi)問(wèn)題(尤其是遞歸問(wèn)題)的一種重要方法
法也稱(chēng)試探法
某一種狀態(tài)
從這種狀態(tài)出發(fā)所能達(dá)到的所有“狀態(tài)
條路走到
時(shí)候(不能再前進(jìn)),再倒
(或若干步),從另一種可能狀態(tài)出發(fā),繼續(xù)搜索,直
的“路徑(狀態(tài))”都試探過(guò)。這種
斷“前進(jìn)”、不斷“回溯”尋找解的方法,稱(chēng)作“回溯法”。它的求解過(guò)程實(shí)質(zhì)上是一個(gè)先根遍歷
棵“狀態(tài)空間樹(shù)”的過(guò)程,只是這棵樹(shù)不是遍歷前預(yù)先建立的,而是隱含在遍歷
探過(guò)程
態(tài)和問(wèn)題所求解產(chǎn)生矛盾時(shí),不再繼續(xù)試探
解的終結(jié)狀態(tài)。否
試探下去便能得到問(wèn)題的角
解、一組
解或最優(yōu)角
這類(lèi)問(wèn)題的
程也可以看成是在給定的(或問(wèn)題蘊(yùn)涵
根遍歷,并在
遍歷過(guò)程中剪去那些不滿(mǎn)足條件的分支的一種搜索算法(深度或?qū)挾?。所以,對(duì)約束條件的分析
題求解的一個(gè)關(guān)鍵之處
解
表示要找一條從A到B的路,我們可以用回溯的思想描述一下求解過(guò)程(不妨借助
圖1找一條從A到B的路
溯法的一般模式
為了應(yīng)用回溯法
的解必須能表
組(
如圖1中的解便
求所有的解滿(mǎn)
明問(wèn)題,先舉
家熟悉的例子
皇后問(wèn)題
要求在8×8格的國(guó)際象棋上擺放8個(gè)皇后,使其不能互相攻
任意兩個(gè)皇后都不處
同
同一斜線(xiàn)上,輸出一種擺
題分析
為了解決這個(gè)問(wèn)題,我們把棋盤(pán)的橫坐標(biāo)設(shè)定為i(
),縱坐標(biāo)設(shè)定
某
)時(shí),在這個(gè)位置的垂直方向、水
和兩條斜線(xiàn)方向都不能再放
后了。圖1便是
題
解(Q表
據(jù)的位置)
圖2八皇后問(wèn)題的一個(gè)解
然,在每
對(duì)每
)都有唯一的
每行
題可以表示成一個(gè)8元組
xs),其中x是放置第
行)皇后的列坐標(biāo)
這個(gè)問(wèn)題的約束條件是:所有的x:都不相同,即所有皇后都
保
在同一條斜線(xiàn)
如圖2的狀態(tài)便滿(mǎn)
束條件
后問(wèn)題的一個(gè)解,可以表示為以
個(gè)
貍鯉開(kāi)
竄蜜
翻圖翻劊鬨眩風(fēng)睏
圖3四皇后問(wèn)題的棋盤(pán)狀態(tài)樹(shù)
圖3是我們將八皇后問(wèn)題簡(jiǎn)化為四皇后問(wèn)題,它展示了求解過(guò)程中棋盤(pán)狀態(tài)的變化
這是一棵四叉樹(shù),樹(shù)上
點(diǎn)表示一個(gè)局部布局或
整的布局,根結(jié)點(diǎn)表示棋盤(pán)的初始
狀態(tài)。每
擇的
任何時(shí)刻,棋盤(pán)的合法
必須滿(mǎn)
兩個(gè)棋子都不能占據(jù)棋盤(pán)上的同一行、或者
或者同一對(duì)角線(xiàn)。我們發(fā)
圖
展開(kāi)的分支結(jié)點(diǎn)中除結(jié)
結(jié)點(diǎn)都不是合法的布局。因此,求四皇后問(wèn)題的所有合法布
過(guò)程,即為在上述約束條件下先根遍
狀態(tài)空間樹(shù)的過(guò)
述出求
后問(wèn)題的回溯算法女
八皇后問(wèn)題的遞歸回溯算法貪心算法
在眾多的計(jì)算機(jī)解題策略中，貪心策略可以算得上是最接近人們?nèi)粘Ｋ季S的一種解題策略，正基于此，貪心策略在各級(jí)各類(lèi)信息學(xué)競(jìng)賽、尤其在對(duì)NPC類(lèi)問(wèn)題的求解中發(fā)揮著越來(lái)越重要的作用。
7.1 貪心策略的定義
貪心策略是：指從問(wèn)題的初始狀態(tài)出發(fā)，通過(guò)若干次的貪心選擇而得出最優(yōu)值(或較優(yōu)解)的一種解題方法。
其實(shí)，從“貪心策略”一詞我們便可以看出，貪心策略總是做出在當(dāng)前看來(lái)是最優(yōu)的選擇，也就是說(shuō)貪心策略并不是從整體上加以考慮，它所做出的選擇只是在某種意義上的局部最優(yōu)解，而許多問(wèn)題自身的特性決定了該題運(yùn)用貪心策略可以得到最優(yōu)解或較優(yōu)解。
例1：在n行m列的正整數(shù)矩陣中，要求從每一行中選一個(gè)數(shù)，使得選出的n個(gè)數(shù)的和最大。
本題可用貪心策略：選n次，每一次選相應(yīng)行中的最大值即可。
例2：在一個(gè)N×M的方格陣中，每一格子賦予一個(gè)數(shù)（即為權(quán)）。規(guī)定每次移動(dòng)時(shí)只能向上或向右?，F(xiàn)試找出一條路徑，使其從左下角至右上角所經(jīng)過(guò)的權(quán)之和最大。
本題用貪心策略不能得到最優(yōu)解，我們以2×4的矩陣為例。
3 4 6
1 2 10
若按貪心策略求解，所得路徑為：1,3,4,6；
若按動(dòng)態(tài)規(guī)劃法求解，所得路徑為：1,2,10,6。
例3:設(shè)定有n臺(tái)處理機(jī)p1，p2，......pn,和m個(gè)作業(yè)j1,j2,...jm,處理機(jī)可并行工作,作業(yè)未完成不能中斷，作業(yè)ji在處理機(jī)上的處理時(shí)間為ti,求解最佳方案,使得完成m項(xiàng)工作的時(shí)間最短
本題不能用貪心算法求解:理由是若n=3,m=6 各作業(yè)的時(shí)間分別是11 7 5 5 4 7
用貪心策略解(每次將作業(yè)加到最先空閑的機(jī)器上)time=15,用搜索策略最優(yōu)時(shí)間應(yīng)是14,但是貪心策略給我們提供了一個(gè)線(xiàn)索那就是每臺(tái)處理上的時(shí)間不超過(guò)15,給搜索提供了方便。
總之：
1. 不能保證求得的最后解是最佳的；
2. 只能用來(lái)求某些最大或最小解問(wèn)題；
3. 能確定某些問(wèn)題的可行解的范圍，特別是給搜索算法提供了依據(jù)。
7. 2 貪心策略的特點(diǎn)
貪心算法有什么樣的特點(diǎn)呢？我認(rèn)為，適用于貪心算法解決的問(wèn)題應(yīng)具有以下2個(gè)特點(diǎn)：
1、貪心選擇性質(zhì)：
所謂貪心選擇性質(zhì)是指應(yīng)用同一規(guī)則f，將原問(wèn)題變?yōu)橐粋€(gè)相似的、但規(guī)模更小的子問(wèn)題、而后的每一步都是當(dāng)前看似最佳的選擇。這種選擇依賴(lài)于已做出的選擇，但不依賴(lài)于未做出的選擇。從全局來(lái)看，運(yùn)用貪心策略解決的問(wèn)題在程序的運(yùn)行過(guò)程中無(wú)回溯過(guò)程。關(guān)于貪心選擇性質(zhì)，讀者可在后文給出的貪心策略狀態(tài)空間圖中得到深刻地體會(huì)。
2、局部最優(yōu)解：
我們通過(guò)特點(diǎn)2向大家介紹了貪心策略的數(shù)學(xué)描述。由于運(yùn)用貪心策略解題在每一次都取得了最優(yōu)解，但能夠保證局部最優(yōu)解得不一定是貪心算法。如大家所熟悉得動(dòng)態(tài)規(guī)劃算法就可以滿(mǎn)足局部最優(yōu)解，但貪心策略比動(dòng)態(tài)規(guī)劃時(shí)間效率更高站用內(nèi)存更少，編寫(xiě)程序更簡(jiǎn)單。
7.3 典型例題與習(xí)題
例4：背包問(wèn)題：
有一個(gè)背包，背包容量是M=150。有7個(gè)物品，物品可以分割成任意大小。
要求盡可能讓裝入背包中的物品總價(jià)值最大，但不能超過(guò)總?cè)萘俊?br/>物品 A B C D E F G
重量 35 30 60 50 40 10 25
價(jià)值 10 40 30 50 35 40 30

分析：
目標(biāo)函數(shù)： ∑pi最大
約束條件是裝入的物品總重量不超過(guò)背包容量：∑wi<=M( M=150)
（1）根據(jù)貪心的策略，每次挑選價(jià)值最大的物品裝入背包，得到的結(jié)果是否最優(yōu)？
（2）每次挑選所占空間最小的物品裝入是否能得到最優(yōu)解？
（3）每次選取單位容量?jī)r(jià)值最大的物品，成為解本題的策略。
程序如下：
program beibao;
const
m=150;
n=7;
var
xu:integer;
i,j:integer;
goods:array[1..n,0..2] of integer;
ok:array[1..n,1..2] of real;
procedure init;
var
i:integer;
begin
xu:=m;
for i:=1 to n do
begin
write('Enter the price and weight of the ',i,'th goods:');
goods[i,0]:=i;
read(goods[i,1],goods[i,2]);
readln;
ok[i,1]:=0; ok[i,2]:=0;
end;
end;
procedure make;
var
bi:array[1..n] of real;
i,j:integer;
temp1,temp2,temp0:integer;
begin
for i:=1 to n do
bi[i]:=goods[i,1]/goods[i,2];
for i:=1 to n-1 do
for j:=i+1 to n do
begin
if bi[i] temp0:=goods[i,0]; temp1:=goods[i,1]; temp2:=goods[i,2];
goods[i,0]:=goods[j,0]; goods[i,1]:=goods[j,1]; goods[i,2]:=goods[j,2];
goods[j,0]:=temp0; goods[j,1]:=temp1; goods[j,2]:=temp2;
end;
end;
end;
begin
init;
make;
for i:=1 to 7 do
begin
if goods[i,2]>xu then break;
ok[i,1]:=goods[i,0]; ok[i,2]:=1;
xu:=xu-goods[i,2];
end;
j:=i;
if i<=n then
begin
ok[i,1]:=goods[i,0];
ok[i,2]:=xu/goods[i,2];
end;
for i:=1 to j do
writeln(ok[i,1]:1:0,':',ok[i,2]*goods[i,2]:2:1);
end.
例5：旅行家的預(yù)算問(wèn)題：
一個(gè)旅行家想駕駛汽車(chē)以最少的費(fèi)用從一個(gè)城市到另一個(gè)城市，給定兩個(gè)城市間的距離d1，汽車(chē)油箱的容量是c，每升汽油能行駛的距離d2，出發(fā)時(shí)每升汽油的價(jià)格是p，沿途加油站數(shù)為n（可為0），油站i離出發(fā)點(diǎn)的距離是di，每升汽油的價(jià)格是pi。
計(jì)算結(jié)果四舍五入保留小數(shù)點(diǎn)后兩位，若無(wú)法到達(dá)目的地輸出“No answer"
若輸入：
d1=275.6 c=11.9 d2=27.4 p=8 n=2
d[1]=102 p[1]=2.9
d[2]=220 p[2]=2.2
output
26.95
本問(wèn)題的貪心策略是：找下一個(gè)較便宜的油站，根據(jù)距離確定加滿(mǎn)、不加、加到剛好到該站。
程序如下:
program jiayou;
const maxn=10001;
zero=1e-16;
type
jd=record
value,way,over:real;
end;
var oil:array[1..maxn] of ^jd;
n:integer;
d1,c,d2,cost,maxway:real;
function init:boolean;
var i:integer;
begin
new(oil[1]);
oil[1]^.way:=0;
read(d1,c,d2,oil[1]^.value,n);
maxway:=d2*c;
for i:=2 to n+1 do
begin
new(oil[i]);
readln(oil[i]^.way,oil[i]^.value);
oil[i]^.over:=0;
end;
inc(n,2);
new(oil[n]);
oil[n]^.way:=d1;
oil[n]^.value:=0;
oil[n]^.over:=0;
for i:=2 to n 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);
begin
cost:=cost+miles/d2*oil[i]^.value;
end;
procedure solve;
var i,j:integer;
s:real;
begin
i:=1;j:=i+1;
repeat
s:=0.0;
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
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
buy(i,oil[j]^.way-oil[i]^.way-oil[i]^.over);
oil[j]^.over:=0.0;
end
else begin
buy(i,maxway-oil[i]^.over);
j:=i+1;
oil[j]^.over:=maxway-(oil[j]^.way-oil[i]^.way);
end;
i:=j;
until i=n;
end;
begin
cost:=0;
if init then begin
solve;
writeln(cost:0:2);
end else writeln('No answer');
end.
例6:n個(gè)部件,每個(gè)部件必須經(jīng)過(guò)先A后B兩道工序。
以知部件i在A,B 機(jī)器上的時(shí)間分別為ai，bi。如何安排加工順序，總加工時(shí)間最短？
輸入：
5
部件 1 2 3 4 5
ai 3 5 8 7 10
bi 6 2 1 4 9
輸出：
34
1 5 4 2 3
本問(wèn)題的貪心策略是A機(jī)器上加工短的應(yīng)優(yōu)先，B機(jī)器上加工短的應(yīng)靠后。
程序如下：
program workorder;
const maxn=100;
type jd=record
a,b,m,o:integer;
end;
var n,min,i:integer;
c:array[1..maxn] of jd;
order:array[1..maxn] of integer;
procedure init;
var i:integer;
begin
readln(n);
for i:=1 to n do
read(c[i].a);
readln;
for i:=1 to n do
read(c[i].b);
readln;
for i:=1 to n do
begin
if c[i].a c[i].o:=i;
end;
end;
procedure sort;
var i,j,k,t:integer;
temp:jd;
begin
for i:=1 to n-1 do
begin
k:=i;t:=c[i].m;
for j:=i+1 to n do
if c[j].m if k<>i then begin temp:=c[i];c[i]:=c[k];c[k]:=temp end
end;
end;
procedure playorder;
var i,s,t:integer;
begin
fillchar(order,sizeof(order),0);
s:=1;
t:=n;
for i:=1 to n do
if c[i].m=c[i].a then begin order[s]:=i;s:=s+1 end
else begin order[t]:=i;t:=t-1;end;
end;
procedure calc_t;
var i,t1,t2:integer;
begin
t1:=0;t2:=0;
for i:=1 to n do
begin
t1:=t1+c[order[i]].a;
if t2 t2:=t2+c[order[i]].b;
end;
min:=t2;
end;
begin
init;
sort;
playorder;
calc_t;
writeln(min);
for i:=1 to n do
write(c[order[i]].o,' ');
writeln;
end.
習(xí)題：
1.最佳瀏覽路線(xiàn)問(wèn)題:
某旅游區(qū)的街道成網(wǎng)格狀（見(jiàn)圖），其中東西向的街道都是旅游街，南北向的街道都是林蔭道。由于游客眾多，旅游街被規(guī)定為單行道。游客在旅游街上只能從西向東走，在林蔭道上既可以由南向北走，也可以從北向南走。阿隆想到這個(gè)旅游區(qū)游玩。他的好友阿福給了他一些建議，用分值表示所有旅游街相鄰兩個(gè)路口之間的道路值得瀏覽得程度，分值從-１００到１００的整數(shù)，所有林蔭道不打分。所有分值不可能全是負(fù)值。
　　例如下圖是被打過(guò)分的某旅游區(qū)的街道圖：
　　
　　 圖6
阿隆可以從任一路口開(kāi)始瀏覽，在任一路口結(jié)束瀏覽。請(qǐng)你寫(xiě)一個(gè)程序，幫助阿隆尋找一條最佳的瀏覽路線(xiàn)，使得這條路線(xiàn)的所有分值總和最大。
2..刪數(shù)問(wèn)題
鍵盤(pán)輸入一個(gè)高精度的正整數(shù)N，去掉其中任意S個(gè)數(shù)字后剩下的數(shù)字按左右次序組成一個(gè)新的正整數(shù)。對(duì)給定的N和S，尋找一種刪數(shù)規(guī)則使得剩下得數(shù)字組成的新數(shù)最小。動(dòng)態(tài)規(guī)劃初步
動(dòng)態(tài)規(guī)劃簡(jiǎn)介
動(dòng)態(tài)規(guī)劃是運(yùn)籌學(xué)的一個(gè)分支
決多階段決策過(guò)程最優(yōu)化問(wèn)題的一種方法。195
年,美國(guó)數(shù)學(xué)家
解決這類(lèi)問(wèn)題的“最優(yōu)化原則
年發(fā)表
的名著《動(dòng)態(tài)規(guī)劃》,該書(shū)是動(dòng)態(tài)規(guī)劃方面的第一本著作。動(dòng)態(tài)規(guī)劃問(wèn)世以來(lái),在工農(nóng)
業(yè)生
程技術(shù)等許多方面都得到
應(yīng)用,取得
的效
動(dòng)態(tài)規(guī)劃
息學(xué)競(jìng)賽是在90年代初期,它以獨(dú)特的優(yōu)點(diǎn)獲
題者的青睞
它就成為了信息學(xué)競(jìng)賽中必不可少
方法
所有的國(guó)內(nèi)和國(guó)際信
競(jìng)賽
至少有一道動(dòng)態(tài)規(guī)劃
動(dòng)態(tài)規(guī)劃
常重要
面,我們先通過(guò)兩個(gè)具體問(wèn)題認(rèn)
例1、攔截導(dǎo)彈(NOIP1999
題描述
某國(guó)為了防御敵
彈襲擊,發(fā)展出一種導(dǎo)彈攔截系統(tǒng)。但是這種導(dǎo)彈攔截系統(tǒng)有
缺陷:雖然它的第一發(fā)炮彈能
任意的高度,但是以后每一發(fā)炮彈都不能高于前一發(fā)
度
雷達(dá)捕捉到敵國(guó)的導(dǎo)彈來(lái)襲
統(tǒng)還在試用階段,所以
統(tǒng)
因此有可能不能攔截所有的導(dǎo)
入導(dǎo)彈
的高度數(shù)據(jù)是不
0000的正整數(shù),每個(gè)數(shù)
至
空格),計(jì)算這套系統(tǒng)最多能攔截多少導(dǎo)彈,如果要攔截所有導(dǎo)彈最少要配備
多少套這種導(dǎo)彈攔截系統(tǒng)
輸入輸出樣例
0
0
6(最多能攔截的導(dǎo)彈數(shù)
要攔截所有導(dǎo)彈最少要配備的系統(tǒng)數(shù)
問(wèn)題分析
我們先解決第
系統(tǒng)最多能攔多少導(dǎo)彈,跟它最后攔截的導(dǎo)彈高度有很大關(guān)系
假設(shè)
枚導(dǎo)彈是第i枚時(shí),系統(tǒng)能攔得的最大導(dǎo)彈數(shù)。例如,樣
果系統(tǒng)攔截的最后一枚
299的話(huà),最多可以攔截第1枚(389)、第
枚(300)、第5枚(299)三枚
最大值就是第一問(wèn)的答案。關(guān)
鍵是怎樣求得a
假設(shè)現(xiàn)在已經(jīng)求得a[1]a
線(xiàn)街校圳的批位味數(shù)的2
系統(tǒng)攔截
攔截的導(dǎo)彈高度必
假如最后第二枚
假如倒數(shù)第
彈是299
類(lèi)似地
當(dāng)然,我們現(xiàn)在求得是以65結(jié)尾的最
彈數(shù)
因此
取所有
的最
類(lèi)似地,我們可以假設(shè)a[1]a[6]為已知,來(lái)求得a
樣,a[6]、a[5]、a[4]、a
2]也是類(lèi)似求法
就
即如果系統(tǒng)攔截的最后1枚
389,則只能攔截第
這樣,求解過(guò)程可以用下列式子歸納
最后,只需把
的最大值輸
這就是第一問(wèn)的解法,這種解題方法就
稱(chēng)為“動(dòng)態(tài)規(guī)劃
第二問(wèn)比較有意
緊接著第
所以很容易受前面的影響,多次采用第
的辦法,然后
數(shù),其實(shí)這是不對(duì)的。要舉反
為7的高度序
不上升序列為
多次求最長(zhǎng)不上升序列的結(jié)果
系
其實(shí)
分別擊落
所以不能用“動(dòng)態(tài)規(guī)劃”做,那
的做法又是什么呢
我們的目標(biāo)是用最
統(tǒng)擊落所有導(dǎo)彈
系統(tǒng)之間怎么分配導(dǎo)彈數(shù)目則無(wú)關(guān)緊
面錯(cuò)誤的想法正是承襲
套系統(tǒng)盡量多攔截導(dǎo)
思維定勢(shì),忽視了最優(yōu)解
系統(tǒng)攔截?cái)?shù)較為平均的
本質(zhì)上是一種貪心算法,但貪心的策略不對(duì)。如果從每套
系統(tǒng)攔截的導(dǎo)彈方面來(lái)想行
我們就應(yīng)該換一個(gè)思路,從攔截某個(gè)導(dǎo)彈所選的系統(tǒng)
題
我
有系統(tǒng)
瞄準(zhǔn)高度必須
犯導(dǎo)彈高度,所
統(tǒng)均無(wú)法攔截
就不得不啟用新系統(tǒng)。如果已有系統(tǒng)中有
攔截該導(dǎo)彈,我
是應(yīng)該繼續(xù)使用
是另起爐灶呢 事實(shí)是:無(wú)論用哪套系統(tǒng)
截了這枚導(dǎo)彈,那
系統(tǒng)的瞄準(zhǔn)高度就等
度,這一點(diǎn)對(duì)舊的或新的系統(tǒng)都適用。而新系統(tǒng)能攔截
彈髙度最高,即新系統(tǒng)的性能優(yōu)于任意一套已使用的系統(tǒng)。既然如此,我們當(dāng)然應(yīng)該選擇
有的系統(tǒng)。如果
統(tǒng)中有多
攔截
隹高度較高的
系統(tǒng)的“潛力”較
較低的系統(tǒng)則不同
打下的導(dǎo)彈別的系統(tǒng)也能打下
到的導(dǎo)彈卻未必是
統(tǒng)所夠不到的。所以,當(dāng)有多個(gè)系統(tǒng)供選擇時(shí),要選瞄準(zhǔn)高
度最低的使用,當(dāng)然瞄準(zhǔn)高度同時(shí)也要」
下當(dāng)前已有系統(tǒng)的各個(gè)當(dāng)前瞄準(zhǔn)高度,該數(shù)組中實(shí)際元素
數(shù)就是第二問(wèn)的解答
[參考程序
ength(line)do(分解
current:=0;(
彈的高度
134

展開(kāi)更多......

收起↑