2024-2025NOIP-算法(中國計算機學會編)

2024-2025NOIP好用算法

中國計算機學會2024

1.模擬方法.................................................................................3

a.用數(shù)學量和圖形描述問題...............................................................3

b.模擬計算過程.........................................................................3

C.模擬時的優(yōu)化.........................................................................3

d.高精度計算算法.......................................................................4

習題....................................................................................5

2.排序算法與算法時空困難度...............................6

a.簡潔排序算法.........................................................................6

b.快速排序、堆排序.....................................................................6

c.算法時空困難度.....................................................................”.7

d.時空的簡潔優(yōu)化方法...................................................................8

e.線性時間排序.........................................................................8

f.歸并排序..............................................................................9

g.合理選用排序算法.....................................................................9

習題.....................................................................................9

3.搜尋.....................................................................................10

a.困難的模擬問題與利用相像性...........................................................10

b.函數(shù)的遞歸調(diào)用......................................................................10

c.棧與深度優(yōu)先搜尋...................................................................“11

d.深度優(yōu)先搜尋的優(yōu)化...................................................................12

仁隊列與廣度優(yōu)先搜尋...................................................................12

f.廣度優(yōu)先搜尋的優(yōu)化.....................................12

習題....................................................................................13

4.貪心方法................................................................................14

a.工程支配模型.........................................................................14

b.部分背包與每步最優(yōu)...................................................................14

C.構(gòu)造貪心算法.........................................................................15

習題....................................................................................15

5.動態(tài)規(guī)劃................................................................................16

a.另一種形式的工程支配.................................................................16

b.記憶化搜尋...........................................................................16

C.數(shù)字三角形：遞推地思索問題...........................................................17

d.石子合并：狀態(tài)的確定.................................................................17

e.街道問題：狀態(tài)量維數(shù)的確定與無后效性..................18

f.0-1背包：奇妙地選取狀態(tài)量..........................................................19

g.Bitonic旅行：最佳的狀態(tài)轉(zhuǎn)化方式...................................................20

h.最長非降子序列模型...................................................................20

i.構(gòu)造動態(tài)規(guī)劃算法...................................................................21

j.動態(tài)規(guī)劃、遞推、廣度優(yōu)先搜尋的區(qū)分與轉(zhuǎn)化............................................21

習題....................................................................................21

6.常用數(shù)學方法...........................................22

2

a.排列組合............................................................................22

b.遞推與通項的選用...................................................................23

7.分治.....................................................................................26

a.子問題與母問題的相像性..............................................................26

b.二分查找.............................................................................26

C.分析算式.............................................................................26

d.最長非降子序列的二分法..............................................................29

8.圖論思想................................................................................30

a.圖論基礎.............................................................................30

b.圖的表示方法........................................................................30

C經(jīng)典圖論算法........................................................................30

d.構(gòu)造圖論模型...........................................32

習題....................................................................................33

附件：關鍵路徑算法、篝火晚會問題解法源文件...........................................33

1.模擬方法

a.用數(shù)學量和圖形描述問題

計算機處理的是數(shù)學量。若要用計算機解決實際問題，須要把實際問題抽象為數(shù)學量，或者數(shù)字。比如,

記事本把文字按ASCH碼表轉(zhuǎn)換為數(shù)字儲存起來，極品飛車把賽車的性能表示為數(shù)字，來權衡賽車的

好壞。一個美麗的算法，須要用數(shù)學量表示出來。

任務：現(xiàn)有兩個軟件工程的制作任務，你的團隊可以接手其中隨意一個?，F(xiàn)要在兩個中選擇一個，須要

考慮制作成本，制作勝利的可能性，可獲得經(jīng)濟收益的多少，對你的團隊知名度的影響等等因素。你

如何量化地分析和解決這個問題？

提示：須要把每一項都轉(zhuǎn)化為數(shù)值，必要時加入權值、計算期望。假如只考慮以上四個因素，可以得到

以下數(shù)學式

綜合收益二制作勝利的概率*［（可獲得經(jīng)濟收益■制作成本）*經(jīng)濟效益的權值+團隊知名度的影響*社會

效益的權值］

其中概率和兩個權值是須要估計的值。

有時，我們須要用更直觀的圖形來描述實際問題。

圖論就是一個絕佳的方法。圖是一種表示離散量間關系的形式，它也是一種思想，常被用于建模。同時,

前人也為我們供應了很多現(xiàn)成的圖論算法，能夠解決很多常見問題，這些將在之后被提到。

矩陣也是一種常見的方法。有時矩陣被表示成三角形的形式，比如"楊輝三角"。矩陣常常和數(shù)學有關,

在計算機計算時常常利用矩陣的遞推式。這也將在后面被提到。

b.模擬計算過程

模擬方法是最常見、最干脆的算法構(gòu)建方法。

任務：編程實現(xiàn)歐幾里得算法(輾轉(zhuǎn)相除法，求兩個數(shù)的最大公約數(shù)gcd(a,b))

提示：

歐幾里得算法原理：gcd(a,b)=gcd(b/amodb)

歐幾里得算法的圖形描述一

|16863||16863|2

I42|

1.寫下兩個數(shù)2.將兩數(shù)相除，余數(shù)寫在較大的數(shù)下面

|16863|2|16863|2

1|4221|1|4221|2——整除

3.將每列最下面的數(shù)相除，余數(shù)寫在被除數(shù)下面4.重復步驟3直至整除，此時最終寫下的余數(shù)即為

起先時兩數(shù)的最大公約數(shù)

這是一個簡潔的模擬算法，實際過程中，量間的關系往往比這困難得多，因而，模擬算法可以是很困難

的。

有些模擬算法還涉及到圖形和其他困難的數(shù)據(jù)結(jié)構(gòu)，這須要我們嫻熟地運用語言，奇妙地把其他關系轉(zhuǎn)

化為數(shù)學量間關系。

c.模擬時的優(yōu)化

假如處理不當，模擬方法寫出的程序會特別長。這要求我們在模擬是將相像的步驟合為一體，適時利用

函數(shù)簡化程序。

以上面的歐幾里得算法為例：

4

/*實現(xiàn)時，若將左邊一列數(shù)最下面的記為七口。0。八右邊一列數(shù)記為RM。。。］,明顯是不明智的，因

為只有每列最終一個數(shù)會在以后的計算中用到*/

/*實現(xiàn)方法一：及每一列最終一個數(shù)分別為L、R.輸入即可是工、R,返回gcd伍,R)*/

intEuclid_l(intL,intR)

for(;;)

(

L=L%R;

if(L==O)returnR;

R=R%L;

if(R==O)returnL;

)

)

/峨們發(fā)覺有兩步是相像的。因而我們可以把它簡化為實現(xiàn)方法二*/

intEuclid_2(intLJntR)

(

intt;

for(;;)

{

t=R;R=L%R;L=t;

if(R==0)returnL;

)

)

/*甚至我們可以寫成遞歸形式。以下是實現(xiàn)方法三?/

intEudid_3(intLJntR)

{

訐(L%R==O)returnR;

elsereturnEuclid_3(R,L%R);

)

這個實例主要體現(xiàn)模擬算法的簡化過程。雖然在這樣小的程序段中，這樣的簡化作用不大，但遇到困難

的模擬問題，這種利用相像性的簡化便特別有用了。應當重視這樣的代碼優(yōu)化。

d.高精度計算算法

競賽中常常會用上一些很大的數(shù)，超出長整型的數(shù)值范圍。這時我們須要運用高精度計算算法。這種算

法可以把數(shù)值范圍增加到我們想要的程度。

高精度函數(shù)往往包括加、減、乘、輸入、輸出五種。

實現(xiàn)高精度計算時，常常運用模擬算法一模擬小學豎式運算。我們把一個高精度數(shù)表示為一個數(shù)組H[],

數(shù)組中的某一個數(shù)相當于高精度數(shù)的某一位。

要留意的是，輸出時往往要求以十進制形式輸出。因而，高精度數(shù)每一位都應便于干脆輸出。這樣，每

一位上的最大數(shù)都應是10人11-1。簡潔地說，若把H口定為unsigned型，高精度數(shù)每一位上最大數(shù)

最好為9999。這樣既能盡量利用儲存空間，又便于輸出。

另外，高精度數(shù)有時會用到負數(shù)。在補碼的體系中，仍舊可以按正數(shù)的方法處理負數(shù)，但是要特殊留意

輸出時的問題，和對溢出的防止。

任務：實現(xiàn)高精度運算加法

提示：設計函數(shù)從末

unsigned*HAdd(unsignedNl[],unsignedN2[]funsignedAns[])?

位起相加，留意是否進位。

明顯，減法作為加法的逆運算，也很簡潔實現(xiàn)。另一種聰慧的方法是，對減數(shù)每一位取補碼，在做加法

5

即可。請讀者自行實現(xiàn)高精度減法。

高精度乘法困難一些。我舉薦的方法是，先考慮多位高精度數(shù)乘一位高精度數(shù)的過程。多位高精度數(shù)乘

多位高精度數(shù)可以轉(zhuǎn)化為多位高精度數(shù)乘另一高精度數(shù)每一位，再將結(jié)果相加的過程。下面紿出多位

高精度數(shù)乘一位高精度數(shù)的源代碼：

#defineH_Bit256/*定義常數(shù)：高精度數(shù)位數(shù)*/

/*N1[J為多位高精度數(shù)

unsigned*HTimesInt(unsignedNl[],intN2runsignedAns[]),

N2為高精度數(shù)的一位，Ans〃為另一高精度數(shù)，用于儲存結(jié)果*/

/倉里允許Ml與Ans相同*/

(

unsignedirup=O;

unsignedlongtemp;

(

temp=Nl[i]*N2+up;

up=temp/10000;

Ans[i]=(unsigned)(temp%10000);

}

returnAns;

/*函數(shù)返回作為答案的高精度數(shù)首地址，這樣更便于高精度運算函數(shù)的運用，例如連乘可以寫成

HTimesInt(HTimesInt(N1[],N2,Ans[]),N3,Ans[])*/

)

高精度數(shù)的輸入輸出須要特地的函數(shù)。針對不同語言的不同特點，可以比較簡潔地寫出這兩個函數(shù)。但

要留意輸出非首位數(shù)位上的"0"。

習題

模擬方法的習題一感謝深藍評測系統(tǒng)供應習題

6

2.排序算法與算法時空困難度

a.簡潔排序算法

簡潔排序算法包括冒泡排序、插入排序、選擇排序。這三種算法簡潔理解、編寫便利，適用于數(shù)據(jù)規(guī)模

較小的情形。

冒泡排序(BubbleSort)的基本思路是：(以從小到大排序為例)從前到后逐個比較相鄰兩數(shù)，若前

數(shù)大于后數(shù)，就將兩數(shù)交換。不斷重復這一過程，直至全部數(shù)字已按從小到大排好。

考慮到好用性的問題，插入排序和選擇排序這里不再介紹。

對于N0IP提高組而言，這些算法時間困難度過高，很難應付較大的數(shù)據(jù)規(guī)模。建議盡量不要采納簡潔

排序算法，除非你特別確信數(shù)據(jù)規(guī)模在可承受范圍之內(nèi)。

b.快速排序、堆排序

快速排序和堆排序是比簡潔排序快的排序算法，在競賽中常常被采納。這里，我們介紹快速排序算法。

堆排序的實現(xiàn)不作介紹，若想了解，可詢問谷歌或百度。

快速排序(Quicksort)基于分治思想。它的基本思路是：(以從小到大排序為例)取一個數(shù)作為標

記元素，將比它大的數(shù)放在它右側(cè)，比它小的數(shù)放在它左側(cè)，再通過遞歸的方法，將左側(cè)的數(shù)用以上

的方法排好，右側(cè)的數(shù)也用以上的方法排好即可。

下面這個視頻能很直觀地比較冒泡排序(BubbleSort)和快速排序(Quicksort)：

在數(shù)據(jù)規(guī)模很大時，平均狀況下快排比冒泡快很多。在處理N0IP提高組含排序的問題時，一般要選擇

快速排序或堆排序。

下面將介紹快速排序的實現(xiàn)(以從小到大排序為例)。

快排運用分治思想，因而要用函數(shù)的遞歸調(diào)用來實現(xiàn)：

voidQuickSort(inta[]rintstjntstp)//這里也可以定義成voidQuicksort(int

len).為了便于理解，我運用前一種寫法。

(

intmid;

mid=partition(a[],stfstp);//partition。用于確定標記元素的位置。

if(l<mid-l)QuickSort(a[]fstfmid-l);

if(mid+1<r)QuickSort(a[],mid+l,stp);

)

現(xiàn)在的關鍵問題在于如何寫partition。。

寫法一：對于數(shù)列567538162

1.取首個元素做標記元素，取出它，令指針p指向最右邊的數(shù)的右邊

——_67538162p-

2.將p向左移動到小于標記元素的數(shù)(或空缺處)為止。若指向空缺，則跳到5；否則將該數(shù)和p移到

空缺處——p-26753816.

3.將p向右移動到大于標記元素的數(shù)(或空缺處)為止。若指向空缺，則跳到5；否則將該數(shù)和p移到

空缺處——2.753816p-6

4.重復2和3。

2p-17538.66

21.538p-766

7

21p-35_8766

5.把標記元素放入空格處——2135p-58766

寫法二：寫法二比寫法一短一些，但理論上講，寫法二要慢一些(因為所作賦值運算多一些)。下面給

出源代碼與分析：

voidQuickSort(longa[],longstjongstp)//&^^partition〃結(jié)合進QirickSor七〃

中

{

longt,nj,r;

n=a[st];

I=st+1;

r=stp;

for(;;)

{

for(;a[l]<=n&&l<=stp;l++);//從右找，找到一個小于標記元素的數(shù)

for(;a[r]>=n&&//從左找，找到一個大于標記元素的數(shù)

if(l>=r)break；//假如]在r右側(cè)，則跳出

t=a[l];a[l]=a[r];a[r]=t;/席換，使小于標記元素的在左，大于標記元素的在右

}

a[st]=a[r];//取出最右側(cè)的小于標記元素的數(shù)寫入空缺

a[r]=n;//空缺處放入標記元素

if(r-st>l)QuickSort(a,st,r-l);

if(stp>l)QuickSort(a,lfstp);

)

以上快排實現(xiàn)方法的最差情形是排列整齊的狀況，這時它的運行效率會很低。為了解決排列整齊的情形,

我們可以運用隨機快速排序法，即隨機選取一個數(shù)作為標記元素(實現(xiàn)時，將其與第一個數(shù)交換即可)。

c.算法時空困難度

為了描述一個算法的優(yōu)劣，我們引入算法時間困難度和空間困難度的概念。

時間困難度：一個算法主要運算的次數(shù)，用0()表示。

通常表示時間困難度時，我們只保留影響最大的項，并忽視該項的系數(shù)。

例如主要運算為賦值的算法，賦值做了3n八3+11八2+8次，則認為它的困難度為0(。人3)；若主要運算為

比較，比較做了4*2An+2*nA4+700次，由于數(shù)據(jù)很大時，指數(shù)級增長的2人11影響最大，我們認為它

的時間困難度為0(2人口)。

常見的時間困難度有下列幾個：

0(n)—貪心算法多數(shù)狀況下為此時間困難度

O(nlbn)—有時帶有分治思想的算法的時間困難度(注Ibn表示以2為底的n的對數(shù))

0(nA2)—有時動態(tài)規(guī)劃的時間困難度

O(nA3)——有時動態(tài)規(guī)劃的時間困難度

0(2八n)—有時搜尋算法的時間困難度

0(n!)一有時搜尋算法的時間困難度

有時時間困難度中含有兩個或多個字母，比如遍歷一個m*n的矩陣，時間困難度為

要留意的是，時間困難度相同的兩個算法，它的實際執(zhí)行時間可能會有數(shù)倍的差距，因而實現(xiàn)時要特殊

留意細微環(huán)節(jié)處的優(yōu)化。

8

NOIP提高組執(zhí)行時限常常為1s.一般認為，將數(shù)據(jù)規(guī)模代入到時間困難度，若所得值小于或接近于

1000000,就是確定平安的、不超時的。

例如，0(。人2)的動態(tài)規(guī)劃算法，可承受的數(shù)據(jù)規(guī)模是nw1000；0(2人n)的搜尋算法，可承受的數(shù)據(jù)規(guī)

模是nw20；O(n!)的搜尋算法，可承受的數(shù)據(jù)規(guī)模是nw9。

事實上，以現(xiàn)在的CPU運行速度，5000000也應當不成問題。

空間困難度：一個算法消耗儲存空間(內(nèi)存)的大小，用0()表示。

空間困難度的表示規(guī)則與時間困難度類似。

在實際應用時，空間的占用是須要特殊留意的問題。太大的數(shù)組常常是開不出來的，即使開出來了，遍

歷的時間消耗也是驚人的。

下面我們簡潔地分析一下簡潔排序算法、快速排序、堆排序的時空困難度。

這三種算法都是基于比較的排序算法，以比較次數(shù)作為主要運算。

簡潔排序算法最差時需做11人2次比較，平均狀況下時間困難度通常被認為是O(n八2)。

快速排序最差時需做|1人2次比較，可以證明平均狀況下需做Mbn次比較，時間困難度是O(nlbn).

堆排序時間困難度是O(Zbn)。

空間上，三者都不須要額外開拓暫存數(shù)組，快排遞歸調(diào)用時須要運用稍多一些的儲存空間。

綜合來看，快速排序、堆排序優(yōu)于簡潔排序算法。

另外，可以證明基于比較的排序算法時間困難度下界為O(nlbn)。

d.時空的簡潔優(yōu)化方法

時間上的優(yōu)化在于少做運算、做耗時短的運算等。

有幾個規(guī)律須要留意：

整型運算耗時遠低于實型運算耗時。

+、?運算特別快(減法是將減數(shù)取補碼后與被減數(shù)相加，其中位運算更快一些，但是減法也比加法稍

慢些。)

*運算比加法慢得多

/運算比乘法慢得多

比較運算慢于四則運算

賦值運算慢于比較運算(因為要寫內(nèi)存)

這些規(guī)律我們可以從宏觀上把握。事實上，原委做了幾步運算、幾次賦值、變量在內(nèi)存還是緩存等多數(shù)

由編譯器、系統(tǒng)確定。

但是，少做運算(尤其在循環(huán)體、遞歸體中)確定能很大程度節(jié)約時間。

下面來舉一個例子：計算組合數(shù)C(m,n)—n件物品取出m件的組合數(shù)。

C(m,n)可用公式干脆計算。C(m,n)=n!/((n-m)!m!),C(m,n)=n(n-l)(n-2)...(n-m+l)/(n-m)!o

明顯，有時所作的乘法少很多，會快一些。

可是這樣算真的最快嗎？

另一條思路是C(m,n)=遞推下去，直到可利用CQ,k)=k=C(k?l,k)為止。

我覺得這種只用加法的運算會快些，盡管加法多一些。(我沒試驗過，你可以去試一下。)

空間上的優(yōu)化主要在于減小數(shù)組大小、降低數(shù)組維數(shù)等。

常用的節(jié)約內(nèi)存的方法有：

壓縮儲存——例：數(shù)組中每個數(shù)都只有0、1兩種可能，則可以按位儲存，空間壓縮為原來的八分之一。

覆蓋舊數(shù)據(jù)一例：矩陣中每一行的值只與上一行有關，輸出只和最末行有關，則可將奇數(shù)行儲存在第一

行，偶數(shù)行儲存在其次行，降低空間困難度。

要留意的是，對空間的優(yōu)化即使不變更困難度、只是變更n的系數(shù)也是極有意義的?？臻g困難度有時對

時間也有影響，要想方設法進行優(yōu)化。

e.線性時間排序

基于比較的排序算法時間困難度下界為O(nlbn).因而，若還要降低困難度，要放棄基于比較的排序

9

算法。

有一類排序算法叫做線性時間排序，它們的時間困難度為O(n)。下面介紹一種。

計數(shù)排序思路：開拓暫存數(shù)組b口，b[k]表示欲排序數(shù)組a口中k出現(xiàn)的次數(shù)(須要遍歷a口)，最終

遍歷b口，可將a口排好。

這種想法特別簡潔，實現(xiàn)也很簡潔。事實證明，在a口取值范圍很?。ㄈ缯头秶r，它是很高效的

排序算法，比快排快不少?？墒莂口取值范圍較大（如長整型范圍）時，它的執(zhí)行時間會變長，而且

數(shù)組b口有時開不出來。

事實上計數(shù)排序時間困難度為O（n+m）,空間困難度也為O（n+m）,m表示a口取值范圍。若m很大，

則也不能在時限內(nèi)執(zhí)行完。

￡.歸并排序

有一種排序時極為常見的情形：有一張成果表，記錄著很多學生的成果，要將他們按成果排序，但成果

相同者的相對依次不能變更。

換句話說，ABCDE五人，A、C、D成果相同，明顯排序完之后會排在一起，現(xiàn)在的要求是：他們排在

起的依次也必需是ACD,不能是ADC、CAD...

這樣的實際問題涉及到排序的穩(wěn)定性。

排序的穩(wěn)定性：一個排序算法，若可使排序前后關鍵字相同的項相對依次不變，則稱該排序算法是穩(wěn)定

的排序算法。

下面我們來考察常見排序算法的穩(wěn)定性。

在編寫合理的狀況下，簡潔排序算法是穩(wěn)定的；快速排序、堆排序是不穩(wěn)定的（你可以好好想想這是為

什么）。

在NOIP中，往往排序是沒有附帶其他項目的，也就不要求排序穩(wěn)定?？焖倥判?、堆排序仍舊是最佳選

擇。

可是有沒有時間困難度為O（nlbn）的穩(wěn)定的排序算法呢？有的。

歸并排序基于分治思想：把要排序的數(shù)組平分兩半，對兩部分分別排序（遞歸地）后再合并起來。合并

時，將一個數(shù)組按依次插入另一個數(shù)組中，須要開拓一個暫存數(shù)組。利用空間優(yōu)化，可只用開拓一個

與原數(shù)組等大的數(shù)組。

歸并排序的源代碼會放在本章的附件中。請讀者自己探討。

歸并排序的優(yōu)缺點都很明顯。無論情形如何，它的比較次數(shù)、賦值次數(shù)都穩(wěn)定在nlbn,沒有最差狀況，

運行時間與快速排序、堆排序相當。而且，它是穩(wěn)定的排序算法。

但是，它的內(nèi)存占用回達到快速排序、堆排序的兩倍，競賽時運用簡潔造成內(nèi)存超出限制。

NOIP初賽曾考察過歸并排序。問題大意是：找出一個算法，使五個數(shù)在n次比較（兩兩比較）后確定

能排定次序，求n的最小值。

在快速排序、堆排序的最差狀況下，須要10次、9次比較?？墒牵\用歸并排序只須要7次！汜?。簹w并

排序沒有最差狀況。

g.合理選用排序算法

下面是本章講過的排序算法的優(yōu)缺點比較：(這里只講最主要的)

排序算法時間困難度優(yōu)點缺點

簡潔排序0m八2)編寫便利執(zhí)行時間長

快排O(nlbn)執(zhí)行時間短很差狀況下執(zhí)行時間長、占用內(nèi)存多

堆排序O(nlbn)執(zhí)行時間短編寫有點麻煩，有較差的狀況

計數(shù)排序O(n+m)編寫便利，取值范圍小時很高效取值范圍大時效率低、易超內(nèi)存限制

歸并排序O(nlbn)穩(wěn)定的排序算法，無較差狀況占用內(nèi)存很大

競賽中首選快速排序、堆排序。但有時也應比較各排序的優(yōu)缺點，依實際合理選用。

習題

排序的習題一感謝深藍評測系統(tǒng)供應習題

10

3.搜尋

a.困難的模擬問題與利用相像性

在講模擬方法時我們講過利用相像性來簡化算法?，F(xiàn)在，我們接著關注這個問題。

搜尋算法是一種"模擬"思維的算法，比較接近平常的思維。與模擬算法相比，它更深刻地利用了相像性。

為了更好地說明，下面舉一個例子：

有一把有n位字母的密碼鎖，每一位上的字母都可從a到Z選取。現(xiàn)密碼被遺忘，開鎖時，請給出一個

便利的方法，使每個字母組合都被嘗試過。

最簡潔想到J的方法便是，按aa…aa，aa...ab,aa...ac,...?aa...az,aa…ba，...?zz...zy,zz...zz這

樣

的字典序來嘗試。

我們可以這樣考慮：

先選定第一位，再選定其次位，……，直到選定第n位，形成一個完整的字母組合。

具體地，在每一位的選取時，都從a起先，到后面位的字母組合全部嘗試過，再跳到下一個字母：若(非

首位)己經(jīng)跳到z而還需再跳一個字母時，就跳到a,同時讓它的前一位跳到下一個字母。

例如，n=3時，形成的字母組合的依次是

aaa-aaa

b-aab

c-aac

z-aaz

ba-aba

b-abb

???

z-abz

ca-aca

??????

zz-azz

baa-baa

??????

zz-bzz

caa-caa

zzz-zzz

以上描述的是一種常見的遍歷方法。

我們留意到，選定每一位的過程是極其相像的。我們須要利用這種相像性。

b.函數(shù)的遞歸調(diào)用

結(jié)構(gòu)化編程語言供應的最大好處無疑是函數(shù)的遞歸調(diào)用。

假如把函數(shù)看成解決某個問題的過程，那么遞歸就可以看成把問題變成相像而更小的問題的過程。留意

這兩個關鍵詞：相像、更小。遞歸的本質(zhì)是利用相像性。

我們接著講上面提到的密碼鎖問題。現(xiàn)在我們要把嘗試過的字母組合都輸出到屏幕上。

我們用遞歸法來完成這個過程。寫遞歸體一般分為兩步：把大問題化成小問題、解決最小問題。

charstring[1000],n;

voidcode(intLeft)//遞歸體，Left表示還須要確定的位數(shù)，這個值隨問題的減小而遞減。

11

if（Left>=l）/力巴大問題化成小問題

for(string[n-Left]="a';string[n-Left]<='z';string[n-Left]++)

code(Left-l);

if（Left==0）//解決最小問題

printf("%s\n",stnng);

)

intmain()

fscanf("%d"f&n);

string[n]='\0';

code(n);

return0;

)

分析這個方法，得知其時間困難度為0（26八n）。

補充一句，上面的過程也可用n個for的嵌套來實現(xiàn)（你能做到嗎？）。

c.我與深度優(yōu)先搜尋

搜尋分為深度優(yōu)先搜尋、廣度優(yōu)先搜尋兩種。下面用樹區(qū)分這兩種搜尋方法。

對于樹，從根節(jié)點起先,查找（遍歷）各節(jié)點，分兩種方式：

從某一節(jié)點向下擴展時,若先遍歷其子節(jié)點，再查找其子節(jié)點的子節(jié)點一廣度優(yōu)先搜尋。

從某一節(jié)點向下擴展時,若遇到子節(jié)點就“深化”到子節(jié)點的子節(jié)點，直到葉子節(jié)點再返回一深度優(yōu)先

搜

索。

對于7頂點的完全二叉樹，兩種方式所到達的頂點依次如下:

11

2325

45673467

廣度優(yōu)先深度優(yōu)先

留意：搜尋面對的數(shù)據(jù)結(jié)構(gòu)往往不是樹。

明顯，深度優(yōu)先搜尋的擴展方式類似于上面敘述的函數(shù)遞歸。這里，我們先分析它。

深度優(yōu)先搜尋在實現(xiàn)時有兩種方式：遞歸形式、非遞歸形式。

遞歸形式利用一個函數(shù)(以整型為例)intcal(...)：

intcal(...)

{

intn;

〃運算

n=cal(…);〃遞歸，常在循環(huán)體中

〃運算

returnn;〃返回

)

非遞歸形式利用一個棧，它可以被看作是遞歸形式的一個變更：

當要遞歸地調(diào)用cal(…)時，不馬上調(diào)用cal(…)，而是將其參數(shù)壓入棧。等函數(shù)運行完，再從棧中彈

出其參數(shù)并再次執(zhí)行函數(shù)cal(…)。

這樣，最終被調(diào)用的最先執(zhí)行。由于后查找的是深度最大的，這樣的結(jié)果是深度優(yōu)先。

深度優(yōu)先搜尋往往采納遞歸方法。

12

一代算法宗師迪杰斯特拉(E.W.Dijkstra)極力推崇遞歸法。它編寫便利、清晰，只是內(nèi)存消耗略

比非遞歸大。非遞歸法往往在擔憂內(nèi)存溢出時運用。

深度優(yōu)先搜尋的巨大優(yōu)勢就是可以領先到達葉子節(jié)點。對于“找出一種方法"、"找出其中一個解”這樣

的

問題有速度上的優(yōu)勢。這里舉例分析。

八數(shù)碼問題；九宮格里有八個分力J填上了數(shù)字1-8,形成最初構(gòu)型。每步只能把空格上下左右的數(shù)之一

與空格對調(diào)?，F(xiàn)要求找出一種方法，使若干步對調(diào)后呈現(xiàn)目標構(gòu)型。例如:

572123

4_1->456

63878_

思路：每次將一個構(gòu)型變?yōu)榱硪粋€，再遞歸地檢查后者能否到達目標構(gòu)型。時間困難度0（4人n）。

偽代碼：

intEightNumbers（構(gòu)型）這里返回步驟數(shù)，若須要知道具體步驟，則用另用棧儲存步驟。

{

同源構(gòu)型則返回32767

同目標構(gòu)型則返回0

n[l]=EightNumbers（變更出的構(gòu)型1）

n[2]=EightNumbers（變更出的構(gòu)型2）

n[3]=EightNumbers（變更出的構(gòu)型3）

n[4]=EightNumbers（變更出的構(gòu)型4）

step=最小值

step為32767貝1返1回32767

返回step+1

}

d.深度優(yōu)先搜尋的優(yōu)化

明顯，以上代碼是可以優(yōu)化的。深搜的優(yōu)化過程也叫"剪枝"?？紤]到好用性，這里我們只講最簡潔的剪

枝方法。

對于上面的偽代碼，將“同源構(gòu)型則返回32767"改為"同己查找構(gòu)型則返回32767”就可以顯著提高效

率。

但是這里須要開拓一個數(shù)組（棧），記錄之前“經(jīng)過”的構(gòu)型。假如想避開遍歷數(shù)組，可以做成哈希表,

而且要壓縮儲存才行。

還有的簡潔方法，編寫的時候自然會想到的。關鍵是要權衡，用這樣的方法所增加的編寫難度是否配得

上所節(jié)約的運行時間。編寫難度增大，調(diào)試的難度也會增大哦。

e.隊列與廣度優(yōu)先搜尋

上面講過用棧來非遞歸地實現(xiàn)深搜。若是把棧改成隊列呢？

經(jīng)過分析，你會發(fā)覺，這樣修改后深搜變成了廣搜！

用這樣的方法可以實現(xiàn)廣搜。

用數(shù)組實現(xiàn)隊列時避開大量元素的移動。實現(xiàn)時，可以先算出隊列元素的上限max,開拓a[max],并

設a[st]為隊列起始(st初值為0),隊列的第i項儲存在a[(st+i-l)%max]。

這樣，出隊列只用將st=(++st%max)即可。

要留意的問題是，廣搜類似于遞推，往往須要開拓空間儲存每一步“遞推"所得到的值。

f.廣度優(yōu)先搜尋的優(yōu)化

廣度優(yōu)先搜尋比較簡潔優(yōu)化，運行時間往往比深搜短一些(不過內(nèi)存占用比深搜大得多)。另外，廣搜

有時可以清晰地反映搜尋深度。

若上面的八數(shù)碼問題改為“現(xiàn)要求找出一種方法，使呈現(xiàn)目標構(gòu)型經(jīng)過的對調(diào)步數(shù)最少”，則用廣搜更好。

13

廣搜常用的優(yōu)化方法：

哈希表法一記錄隊列中已有節(jié)點，用于推斷是否須要擴展節(jié)點。

A*算法一構(gòu)造估價函數(shù)。

雙向廣度優(yōu)先搜尋——從源節(jié)點、目標節(jié)點一起起先搜尋。

由于NOIP提高組近年來幾乎不出搜尋題；可用搜尋的題目，由于搜尋時間困難度太高，數(shù)據(jù)規(guī)模太大，

搜尋只能得部分分數(shù)。加之搜尋思路較簡潔，搜尋法這里不再具體敘述。若想了解，大家可以用搜尋

引擎搜尋。

習題

搜尋的習題一感謝深藍評測系統(tǒng)供應習題

14

4.貪心方法

a.工程支配模型

我們常常遇到這樣的問題：完成一個工程須要若干個步驟，每個步驟都有若干種方法，圖示一

步驟a步驟b步驟c…步驟n

方法bl方法cl

方法al方法b2方法c2方法nl

方法a2方法b3方法c3

方法c4

每個方法有一個權值（如效率、質(zhì)量），其大小往往和其他步驟中選取的方法有關。有些時候權值無意

義，表示方法不行選擇。要求給出一個方法組合，是權值和最大。

在這里，暫且把它稱作“工程支配"。很多實際問題都可以歸納為這個模型。

對于不同形式的工程支配，我們有不同的解法。

若權值與整個過程或前后步驟的方法選擇都有關，我們運用搜尋算法一時間困難度高得嚇人。

若每個權值只與上（或下）一步或少數(shù)幾步的方法選擇都有關，我們運用動態(tài)規(guī)劃一有比較高的效率，

在下一章會講到。

若每個權值與其他步驟的方法選擇都沒有關系，我們運用貪心方法。

b.部分背包與每步最優(yōu)

強調(diào)：每個權值與其他步驟的方法選擇都沒有關系。這樣每步最優(yōu)就可以得到全局最優(yōu)一每一步都取最

大的權值就可以了。

換而言之，貪心算法要求，局部的貪心選擇，可以組成全局的最優(yōu)解。

在實際問題中，這是須要證明的。假如這個無法證明，貪心算法所得的解不是最優(yōu)解，一般只是較優(yōu)解

（較優(yōu)解可為搜尋剪枝供應便利）。

下面是貪心算法最經(jīng)典的例子：部分背包問題。（下一章會講到另外兩種背包問題。）

問題：有N件物品和一個最大載重為M的背包，每件物品都有相應的重量和價值?，F(xiàn)要求給出一個存放

方案，使背包中物品總價值最大。部分背包要求，每件物品都可只裝入它的一部分（部分重量有成比

例的部分價值）。所涉及到的數(shù)字均為整數(shù)。

（注：有時該問題表述為體積形式，即背包體積有限，每件物品有體積和價值。在本系列我選擇表述為

重量形式。）

思路：背包中物品總價值最高，即單位重量物品價值最高。明顯，應當多裝單位重量價值高的物品。這

樣，我們先裝入單位重量價值最高的物品，再裝入其次高的……直到重量達到M（有必要時最終一件物

品只裝一部分），己達到物品總價值最高。

這個證明應當很嚴謹吧?

該算法時間困難度0（n）,效率很高；而且實現(xiàn)很簡潔。這些是貪心法最大的特點。

很多競賽題看似可以用貪心法，其實貪心法得不到最優(yōu)解，緣由是每一步的選擇對其他步驟有影響。

數(shù)字三角形問題：有一個數(shù)字三角形（如下圖）。現(xiàn)有一只螞蟻從頂層起先向下走，每走下一級時，可

向左下方向或右下方向走。求走究竟層后它所經(jīng)過的數(shù)的最大值。

1

63

826

2165

32476

假如用貪心法，每次向最大的方向走，得到結(jié)果為1+6+8+2+3=20?？墒敲髅鬟€有另一條路，

1+3+6+6+7=23。

15

問題出在哪？每次的選擇對后面的步驟會有影響！第三級選了8,就選不到第四、五級較大的數(shù)了。

這個問題正確的解法會在下一章介紹。

有一個很好用的小技巧：競賽題會給出數(shù)據(jù)規(guī)模。通過數(shù)據(jù)規(guī)模，我們可以大致推斷該用何種算法。貪

心算法可承受的數(shù)據(jù)規(guī)模很大，一般都會上萬。假如給出的數(shù)據(jù)規(guī)模是100或1000,優(yōu)先考慮動態(tài)規(guī)

劃吧。

c.構(gòu)造貪心算法

構(gòu)造與證明是貪心算法的難點，常常要求我們要有敏銳的視察力、多角度思索的變通實力、豐富的數(shù)學

學問和推理實力。

下面舉幾個貪心算法的例子，供大家揣摩、駕馭規(guī)律。

刪數(shù)問題：給出一個N位的十進制高精度數(shù)，要求從中刪掉S個數(shù)字（其余數(shù)字相對位置不得變更），

使剩余數(shù)字組成的數(shù)最小。

算法構(gòu)造：

1.每次找出最靠前的這樣的一對數(shù)字一兩個數(shù)字緊鄰，且前面的數(shù)字大于后面的。刪除這對數(shù)字中靠前

的一個。

2.重復步驟1,直至刪去了S個數(shù)字或找不到這樣的一對數(shù)。

3.若還未刪夠S個數(shù)字，則舍棄末尾的部分數(shù)字，取前N?S個。

證明思路：明顯，在只刪一個數(shù)字時，唯有步驟1的方法能使數(shù)變??；可推理得出，刪多個數(shù)字時，所

有最優(yōu)的方法都可看做是對步驟1的重復。也就是說，以上方法是最優(yōu)策略之一。

在文末的附件中給出了這個算法的源代碼。

工序問題：n件物品，每件需依次在A、B機床上加工。已知第i件在A、B所需加工時間分別為A[i]、

B[ib設計一加工依次，使所需加工總時間最短。

算法構(gòu)造：

1.設置集合F、M、S；先加工F中的，再加工M中的，最終加工S中的。

2.對第i件，若A[i]B[i],則歸入S；若A[i]=B[i],則歸入M。

3.對F中的元素按A[i]升序排列，S中的按B[i]降序排列。

證明思路：

1.F中的能“拉開"A、B加工同一件工件的結(jié)束時刻，為后面的工件加工“拉開時間差”，利于節(jié)約總

時

間。S中的剛好相反。因而，F(xiàn)中元素放在最前確定是最優(yōu)策略之一。

2.F中A川小的前置，可以縮短起先時B的空閑時間，但會使F全部工件”拉開的時間差”縮短。不過

可以證明，后者帶來的損失不大于前者獲得的優(yōu)勢。對稱地，對S也一樣。因而步驟3是可行的。

種樹問題：一條街道分為n個區(qū)域（按l-n編號），每個都可種一棵樹。有m戶居民，每戶會要求在區(qū)

域i?j區(qū)間內(nèi)種至少一棵樹?，F(xiàn)求一個能滿意全部要求且種樹最少的方案。

算法構(gòu)造：

1.對于要求，以區(qū)間右端（升序）為首要關鍵字，左端（升序）為次要關鍵字排序。

2.按排好的序依次考察這些要求，若未滿意，則在其最右端的區(qū)域種樹，這時可能會滿意多個要求。

證明思路：解法并不唯一，關鍵是證明沒有比該解法更好的解法。按步驟1排序之后，會發(fā)覺對于每個

要求，在最右邊的區(qū)域內(nèi)種樹所得的結(jié)果總不會差于在其他區(qū)域種樹。至于為什么這樣排序，留給你

—讀者們思索吧。

在文末的附件中給出了這個算法的源代碼。

習題

貪心方法的習題一感謝深藍評測系統(tǒng)供應習題

16

5.動態(tài)規(guī)劃

a.另一種形式的工程支配

b.記憶化搜尋

c.數(shù)字三角形：遞推地思索問題

d.石子合并：狀態(tài)的確定

e.街道問題；狀態(tài)量維數(shù)的確定與無后效性

f.o-l背包：奇妙地選取狀態(tài)量

g.Bitonic旅行：最佳的狀態(tài)轉(zhuǎn)化方式

h.最長非降子序列模型

i.構(gòu)造動態(tài)規(guī)劃算法

j.動態(tài)規(guī)劃、遞推、廣度優(yōu)先搜尋的區(qū)分與轉(zhuǎn)化

a.另一種形式的工程支配

上一章我們講過，若工程支配問題中某一步權值只和上一步或少數(shù)幾步的選擇有關，我們可以運用效率

較高的動態(tài)規(guī)劃算法。

看下面這個問題：

4-9

/\

1-2-5-3-1

\\//

1-7-8

上圖的數(shù)字間連了線。現(xiàn)要從最左邊的"1"走到最右邊的“1"，每次都只能沿線向右走到右邊一列的某

個數(shù)上，要求找出一條路徑，路徑上的五個數(shù)之和最大。

當然我們可以把這理解為工程支配問題的一種形式。

這里，每一步的選擇與上一步相關；好像也與前面幾步的選擇有關，但是留意，前幾步的影響都可以表

現(xiàn)在上一步上，上一步方法的選擇已經(jīng)可以獨立確定這一步每種選擇的權值。此處適用動態(tài)規(guī)劃。

換句"專業(yè)”點的話，這里滿意“無后效性原則”，即之后過程不受之前具體過程的影響。這在后面會具

體

說明。

b.記憶化搜尋

再講動態(tài)規(guī)劃之前，我們先接觸一下記憶化搜尋。

留意到，在深度優(yōu)先搜尋中，用于遞歸的函數(shù)cal(…)有時會被用同樣的參數(shù)調(diào)用多次。你可能很簡潔

想到，假如在第一次調(diào)用時把參數(shù)和對應的函數(shù)值儲存起來，若以后再以同樣的參數(shù)調(diào)用，就不用執(zhí)

行遞歸函數(shù)，干脆取出所得的值，不是快得多？

假如你能想到這些，你就已經(jīng)學會記憶化搜尋了。

事實上，記憶化搜尋能大幅提高效率的地方，往往是在動態(tài)規(guī)劃的題目中。

動態(tài)規(guī)劃能解決的問題，往往可以用記憶化搜尋替代動態(tài)規(guī)劃解決。假如你實在無法駕馭動態(tài)規(guī)劃，你

可以選擇運用記憶化搜尋。不過你要留意以下事實：

動態(tài)規(guī)劃程序?qū)崿F(xiàn)較簡潔，程序段短，便于調(diào)試；記憶化搜尋實現(xiàn)就比較繁瑣。

雖然記憶化搜尋可以把時間困難度降低到動態(tài)規(guī)劃的水平，但是實際執(zhí)行時間會大于動態(tài)規(guī)劃，甚至有

幾倍到十幾倍的差距。

這里不給出記憶化搜尋的代碼了。我們還是首選動態(tài)規(guī)劃吧?

17

c.數(shù)字三角形：遞推地思索問題

上一章中我們講過數(shù)字三角形問題：

有一個數(shù)字三角形（如下圖）?，F(xiàn)有一只螞蟻從頂層起先向下走，每走下一級時，可向左下方向或右下

方向走。求走究竟層后它所經(jīng)過的數(shù)的最大值。

1

63

826

2165

32476

對于這個問題，貪心法得不到最優(yōu)解，搜尋法效率太低。我們知道，深度優(yōu)先搜尋利用了遞歸式的思維，

動態(tài)規(guī)劃中，我們運用遞推式的思維。

遞歸：要知道第五層時的最大值，就要知道第四層時的最大值；要知道第四層時的最大值，就要知道第

三層時的最大值……而每一步推導的方法是相像的。

遞推：知道第一層的最大值，就能知道其次層的最大值，也就能知道第三層的最大值……而每一步推導的

方法是相像的。

對比之下，遞推思維不是從結(jié)論入手的，有時簡潔失去方向；但是有時卻可以有很高的效率。

動態(tài)規(guī)劃和一般遞推的區(qū)分在于動態(tài)規(guī)劃須要在每一步作比較、取最優(yōu)值。

對于數(shù)字三角形問題，我們可以這樣思索：設二維數(shù)組表示走到第i行的第j個數(shù)時所經(jīng)

過的數(shù)字和的最大值。例如對圖中三角形，A[3][2]=max{l+6+2,l+3+2}o

這樣，我們又可以得到遞推關系A[i]m=p[i]U]+max{A[i?l]rl],A[i?l]m}（實現(xiàn)時注

意或不存在時的處理），其中表示第i行的第j個數(shù)的數(shù)值。

此外，我們還須要一些初始值：p[i][jl（輸入），A[l][l]=p[l][l]o

最終我們可以求出A[5][j],結(jié)論自然是max{A[5]皿}啦?

分析這個算法，若層數(shù)大于5,則時間困難度為O（n人2）。若用搜尋，時間困難度為0（2八11）。明顯動態(tài)

規(guī)劃效率高很多。

為了更清晰地說明動態(tài)規(guī)劃算法，我們先引入一些概念。

階段一我們把問題劃分為幾步，在動態(tài)規(guī)劃中，這叫做"劃分階段"。數(shù)字三角形中，每一層可看作是

個階段。

狀態(tài)一每一階段有多種選擇，不同的選擇會有不同的結(jié)果，我們把每階段的不憐憫形叫做“狀態(tài)"。每

階段包括多個狀態(tài)。數(shù)字三角形中，表示走到第j個數(shù)時所經(jīng)過的數(shù)字和的最大值的變量叫做狀態(tài)。

動態(tài)轉(zhuǎn)移方程一我們可以用一個遞推式表示某階段到下一階段的遞推關系，這個遞推式叫做動態(tài)轉(zhuǎn)移方

程。動態(tài)轉(zhuǎn)移方程一般含有max?；騧in{}。

決策一即對方法的選擇。每個階段都有一個決策。這樣的選擇是有范圍的，這個范圍叫做“決策允許集

合”。

策略一一套完整的決策的組合?！白顑?yōu)策略”即最佳的決策組成的策略。

還有一些概念因為運用較少，這里不再具體介紹。

留意可以運用動態(tài)規(guī)劃解決的問題的兩個必需特性：

最優(yōu)化原理一簡潔地說，最優(yōu)策略某幾個連續(xù)階段上的決策組合，也是這幾個階段組成的子問題的最優(yōu)

策略。

無后效性原則一某階段以后的決策，與該階段之前的具體決策無關，只與該階段的狀態(tài)有關。

留意，有些時候我們認為不滿意這兩點的問題，換個角度看又是滿意的。這正是動態(tài)規(guī)劃的4點。接下

來我們就是要找尋合適的角度，找出滿意這兩個關系的算法。

d.石子合并：狀態(tài)的確定

用動態(tài)規(guī)劃解決問題，首要也是最重要的步驟就是劃分階段、確定狀態(tài)。這確定了是否能勝利運用動態(tài)

規(guī)劃方法。因此。確定一個可行的遞推思路是勝利的關鍵。

18

在這一過程中，要擅長變通。

石子合并：N堆石子圍成一圈，每堆石子的量a[i]己知.每次可以將相鄰兩堆合并為一堆，將合并后

石子的總量記為這次合并的得分。N?1次合并后石子成為一堆。求這N?1次合并的得分之和可能的最大

值。

數(shù)據(jù)規(guī)模：N<100,a[i]<20000000

算法構(gòu)造：

分析數(shù)據(jù)規(guī)模一算法可承受的最大數(shù)據(jù)規(guī)模O(N^3),搜尋必定超時，貪心可承受數(shù)據(jù)規(guī)模太大，優(yōu)先

考慮動態(tài)規(guī)劃。

遞推思路一計算將第i堆至第j堆完全合并所能獲得的最大得分。這是此題的關鍵。考慮模擬每種合并

后的具體情形是行不通的。把問題變成這樣后就好解決了。

劃分階段一以合并的次數(shù)作為標準劃分階段。

確定狀態(tài)一第i堆至第j堆合并所能獲得的最大價值。

狀杰轉(zhuǎn)移方程---f(ij)=max{f(i,k)+f(k+lj)}rO<i<k<j^n

邊界狀態(tài)——f(ij)=a[i]

分析知時間困難度為。8人3),滿意要求。

遞推求出f(l,n)即可。動態(tài)規(guī)劃特點是“思路難，實現(xiàn)易“，這里不再給出源代碼。

另外，NOIP2024出現(xiàn)了一道石子合并的衍生問題。

在Mars星球上，每個Mars人都隨身佩帶著一串能量項鏈。在項鏈上有N顆能量珠。能量珠是一顆有

頭標記與尾標記的珠子，這些標記對應著某個正整數(shù)。并且，對于相鄰的兩顆珠子，前一顆珠子的尾

標記確定等于后一顆珠子的頭標記。因為只有這樣，通過吸盤(吸盤是Mars人汲取能量的一種器官)

的作用，這兩顆珠子才能聚合成一顆珠子，同時釋放出可以被吸盤汲取的能量。假如前一顆能量珠的

頭標記為m,尾標記為r,后一顆能量珠的頭標記為r,尾標記為n,則聚合后釋放的能量為(Mars

單位)，新產(chǎn)生的珠子的頭標記為m,尾標記為n。

須要時，Mars人就用吸盤夾住相鄰的兩顆珠子，通過聚合得到能量，直到項鏈上只剩下一顆珠子為止。

明顯，不同的聚合依次得到的總能量是不同的，請你設計一個聚合依次，使一串項鏈釋放出的總能量

最大。

建議讀者自己思索解決，以熟識動態(tài)規(guī)劃的思維過程。在附件中給出解法的源代碼。

e.街道問題：狀態(tài)量維數(shù)的確定與無后效性

下面是動態(tài)規(guī)劃的經(jīng)典問題之一：街道問題。

下圖表示一個街道。現(xiàn)有類似這樣的N*N的街道，且每段路有一個權值?，F(xiàn)在要從左上角沿線走到右下

角，每次只能向右或向下走。求經(jīng)過路段權值和的最大值。

數(shù)據(jù)規(guī)模：N<1000

3256

IIIII

4|3728

2|3682

卜3+++T

6|8514

HH-5-+9-1-8-4

9|3281

分析數(shù)據(jù)規(guī)模一算法可承受的最大數(shù)據(jù)規(guī)模O（N人2）,搜尋必定超時，貪心可承受數(shù)據(jù)規(guī)模太大，優(yōu)先

考慮動態(tài)規(guī)劃。

遞推思路一從左上角向右下角推，求出走到每一點所經(jīng)過權值和的最大值。

劃分階段一按斜向（/）劃分

19

剩下的讀者自己思索。時間困難度應為0（n八2）。

上面問題中，若是改為從左上角沿線走到右下角再以不交叉的線路返回到動身點，算法應當做怎樣的修

改？

原來的狀態(tài)已經(jīng)不能保證"不交叉”，在這種狀況下，我們用增加一維狀態(tài)量的方法，以探討是否交叉，

比較便利的思路一從左上角動身兩條路，再向右下方遞推的過程中，兩條路的最末端始終不能是同一點,

必需分布在這一階段的兩點上，直到最終在右下角匯合。

由于增加了一維狀態(tài)量，時間困難度變?yōu)?（n人3）。

f.0-1背包：奇妙地選取狀態(tài)量

有時，選定狀態(tài)時發(fā)覺不能運用動態(tài)規(guī)劃，或問題從表面上看讓人無所適從，我們不妨從另一個角度看

問題。

上一章我們介紹了部分背包問題，下面我們介紹更經(jīng)典的背包問題。

問題描述：有N件物品和一個最大載重為M的背包，每件物品都有相應的重量和價值?，F(xiàn)要求給出一個

存放方案，使背包中物品總價值最大。所涉及到的數(shù)字均為整數(shù)。

數(shù)據(jù)規(guī)模：1<N<1OO,l<M<10000o

這個問題與部分背包問題的區(qū)分在于，物品只能整件放入，不能只取一部分。這樣，背包很可能會有部

分載重量未利用。若用貪心法取單位重量價值高的，可能會使背包未利用的載重上升，得不到最優(yōu)方

案。

考慮到數(shù)據(jù)規(guī)模，選用動態(tài)規(guī)劃法。

好像只有“每考慮一件物品為一階段”的劃分方法?？墒侨绾未_定狀態(tài)？很多人想不到這個方法：以一個

最大載重值為一個狀態(tài)。

完整遞推思路——