深搜與簡單的動態(tài)規(guī)劃

深搜與簡單的動態(tài)規(guī)劃第1頁，課件共48頁，創(chuàng)作于2023年2月深度優(yōu)先搜索算法的框架:proceduredfs(i);//搜索第i個分量Xibeginifi=n+1找到一個解

//ifi=n+1thenexit;//防止數(shù)組越界

//合適的剪枝優(yōu)化：最優(yōu)化剪枝與可行性剪枝forXi

∈Si且使得（X1,X2，。。。Xi-1,Xi）滿足約束條件dobegin記錄滿足條件的Xi;//添加相應(yīng)的標(biāo)志;dfs(i+1)//刪除標(biāo)志;恢復(fù)之前的狀態(tài),根據(jù)具體情況選擇:回溯endend第2頁，課件共48頁，創(chuàng)作于2023年2月1、數(shù)字三角形

有一個數(shù)字三角形，編程求從最頂層到最底層的一條路所經(jīng)過位置上數(shù)字之和的最大值。每一步只能向左下或右下方向走。下圖數(shù)據(jù)的路應(yīng)為7->3->8->7->5，和為30。輸入：第一行：R(1<=R<=100),數(shù)字三角形共有R行；以下R行：依次表示數(shù)字三角形中每行中的數(shù)字。每個數(shù)都是非負(fù)的，且<=100.輸出：一個正整數(shù)，路徑上數(shù)字之和的最大值。輸入樣例：5738810274445265輸出樣例：30

738810274445265第3頁，課件共48頁，創(chuàng)作于2023年2月算法1：深度優(yōu)先搜索算法DFS：二維數(shù)組a[i，j]存儲數(shù)字三角形。Proceduredfs(sum,i,j:integer);//從a[1,1]到走到第i行第j列即a[i,j]時所取得的值為sumbeginifi=nthenbeginifsum>maxthenmax:=sum;exit;end;

dfs(sum+a[i+1,j],i+1,j);//向左下方走

dfs(sum+a[i+1,j+1],i+1,j+1);//向右下方走end;開始時：dfs(a[1,1],1,1);結(jié)果：max

738810274445265第4頁，課件共48頁，創(chuàng)作于2023年2月

738810274445265為什么當(dāng)n較大時速度慢？f:array[0..100,0..100]ofinteger;f[i,j]:(i,j)到最后一行經(jīng)過數(shù)的和的最大值f[i,j]:=max(f[i+1,j],f[i+1,j+1])+a[i,j];初始：f[n,i]=a[n,i]目標(biāo)：f[1,1]第5頁，課件共48頁，創(chuàng)作于2023年2月算法2：functionmax(a,b:longint):longint;beginifa>bthenexit(a)elseexit(b);end;Proceduredfs(i,j:integer);

//求(i,j)到最后一行的最大和

beginifi=nthenbeginf[i,j]:=a[i,j];exit;end;iff[i,j]>0thenexit;dfs(i+1,j);dfs(i+1,j+1);f[i,j]:=max(f[i+1,j],f[i+1,j+1])+a[i,j];end;第6頁，課件共48頁，創(chuàng)作于2023年2月Begininit;fillchar(f,sizeof(f),0);dfs(1,1);writeln(f[1,1]);End.第7頁，課件共48頁，創(chuàng)作于2023年2月設(shè)f[i,j]:a[i,j]到達(dá)第n行a[n,k]（k：1..n）的最大值．遞推關(guān)系：f[i,j]=max{f[i+1,j],f[i+1,j+1]｝+a[i,j]初始：f[n,i]:=a[n,i];1=<i<=n目標(biāo)：f[1,1]算法3：

73881027

4445265第8頁，課件共48頁，創(chuàng)作于2023年2月proceduremain;beginfori:=1tondof[n,i]:=a[n,i];fori:=n-1downto1do{枚舉行}forj:=1toido{枚舉每行的元素}

f[i,j]:=max(f[i+1,j],f[i+1,j+1])+a[I,j];{枚舉走法}writeln(f[1,1]);end;

functionmax(a,b:integer):integer;beginmax:=a;ifb>maxthenmax:=b;end;第9頁，課件共48頁，創(chuàng)作于2023年2月依次求從起點(diǎn)(1,1)到點(diǎn)（i，j）的最大值。//正向設(shè)f[i,j]為從a[1,1]到達(dá)a[i,j]時取得的最大值．根據(jù)題意可得出遞推關(guān)系：f[i,j]=max{f[i-1,j-1],f[i-1,j]｝+a[i,j]初始：f[1,1]:=a[1,1];目標(biāo)：max{f[n,i]}1=<i<=n

73881027

4445265

算法4：第10頁，課件共48頁，創(chuàng)作于2023年2月proceduremain;{順推}beginf[1,1]:=a[1,1];fori:=2tondoforj:=1toidof[i,j]:=max(f[i-1,j-1],f[i-1,j])+a[i,j];ans:=f[n,1];fori:=2tondoiff[n,i]>ansthenans:=f[n,i];writeln(ans);end;第11頁，課件共48頁，創(chuàng)作于2023年2月總結(jié)：算法1：一般的搜索（效率很低）。算法2：記憶化搜索（效率高）。算法3和算法4：動態(tài)規(guī)劃算法（效率高）。第12頁，課件共48頁，創(chuàng)作于2023年2月在一個n*m的棋盤內(nèi)，一些格子里有垃圾要拾撿?，F(xiàn)在有一個能撿垃圾的機(jī)器人從左上格子里出發(fā)，每次只能向右或者向下走。每次他到達(dá)一個點(diǎn)，就會自動把這個點(diǎn)內(nèi)的垃圾拾掉。問：機(jī)器人到達(dá)右下角時最多能拾多少垃圾。數(shù)據(jù)范圍:n<=100,m<=1002、Robots機(jī)器人撿垃圾第13頁，課件共48頁，創(chuàng)作于2023年2月樣例輸入：67712142426444766樣例輸出：5第14頁，課件共48頁，創(chuàng)作于2023年2月算法1：dfsC[i,j]=1表示(i,j)點(diǎn)有垃圾。C[i,j]=0表示沒有。proceduredfs(i,j,sum:longint);//從(i,j)走到終點(diǎn)(n,m)能撿到的垃圾數(shù)是sumbeginif(i=n)and(j=m)thenifsum>ansthenans:=sum;ifi<nthendfs(i+1,j,sum+c[i+1,j]);ifj<mthendfs(i,j+1,sum+c[i,j+1]);end;初始：dfs(1,1,c[i,j])結(jié)果是：ans第15頁，課件共48頁，創(chuàng)作于2023年2月算法2:因?yàn)橹荒芟蛴一蛘呦蛳伦?。也就是說不能走回頭路。設(shè)f[i,j]表示從(1,1)點(diǎn)開始走到(i,j)的時候，最多撿了多少垃圾。根據(jù)(i,j)只能從(i-1,j)或者(i,j-1)走過來。得出遞推關(guān)系:f[i,j]=Max{f[i-1,j],f[i,j-1]}+c[i,j]初始：f[0,i]=0;0<=i<=m;f[j,0]=0;0<=j<=n;目標(biāo)：f[n,m]第16頁，課件共48頁，創(chuàng)作于2023年2月簡單的主程序：Fillchar(f,sizeof(f),0);fori:=1tondoforj:=1tomdof[i,j]:=max(f[i,j-1],f[i-1,j])+c[i,j];Writeln(f[n,m]);第17頁，課件共48頁，創(chuàng)作于2023年2月3：簡單的背包問題(0-1背包)

設(shè)有ｎ種物品，每種物品有一個重量及一個價值。同時有一個背包，最大載重量為M，今從ｎ種物品中選取若干件，使其重量的和小于等于m，而價值的和為最大。N<=100,M<1000.

輸入數(shù)據(jù)：

第一行兩個數(shù)：物品總數(shù)Ｎ，背包載重量M；兩個數(shù)用空格分隔；

第二行N個數(shù),為Ｎ種物品重量Wi(<1000)；兩個數(shù)用空格分隔；

第三行N個數(shù),為N種物品價值Vi(<1000);兩個數(shù)用空格分隔；

輸出數(shù)據(jù)：

總價值；輸入樣例1：

410

4357

1572025

輸出樣例1：

35輸入樣例2：

420

291015

291016

輸出樣例2：

19第18頁，課件共48頁，創(chuàng)作于2023年2月Dfs算法:constmaxn=100;varn,m:integer;//n：物品數(shù)量；m：背包容量

w:array[1..maxn]ofinteger;//物品重量

v:array[1..maxn]ofinteger;//物品價值

best:longint;//最大價值

第19頁，課件共48頁，創(chuàng)作于2023年2月proceduredfs(i,left,value:longint);//i：搜索第i件物品:判斷放還是不放到背包里

//left：背包的剩余空間

//value：已裝物品的價值

beginifi=n+1thenifvalue>bestthenbest:=value;

ifi>nthenexit;//防止溢出

dfs(i+1,left,value);//不裝iifleft>=w[i]then//裝i

dfs(i+1,left-w[i],value+v[i]);end;第20頁，課件共48頁，創(chuàng)作于2023年2月主程序：

init;dfs(1,m,0);writeln(best);第21頁，課件共48頁，創(chuàng)作于2023年2月0123456789100000000000001000015151515151515200071515152222222230007152020222735354000715202025273535背包的容量0--10物品0--4編號1234容量4357價值15720254件物品背包容量：10算法2：設(shè)f[i,j]:從1到i件物品中選若取干件放到容量為j的背包中，獲得的最大價值。目標(biāo)是：f[n,m]第22頁，課件共48頁，創(chuàng)作于2023年2月用f[i,j]表示在第１到第i件物品中裝入重量為j的背包獲得的最大價值．f[i,j]=max{f[i-1,j],f[i-1,j-W[i]]+V[i]}(1<=i<=n,1<=j<=m)目標(biāo)：f[n,m];2)f[i-1,j-W[i]]+V[i]：放第i件的價值。條件：j>=w[i]1)f[i-1,j]:不放第i件物品獲得的價值。第23頁，課件共48頁，創(chuàng)作于2023年2月主程序：

fillchar(f,sizeof(f),0);fori:=1tondo

forj:=1tomdobeginf[i,j]:=f[i-1,j];

//不選擇第i件物品

if(j>=w[i])and(f[i,j]<f[i-1,j-w[i]]+v[i])//選擇第i件物品｝

thenf[i,j]:=f[i-1,j-w[i]]+v[i];end;writeln(f[n,m]);end.第24頁，課件共48頁，創(chuàng)作于2023年2月4：求最大連續(xù)子序列的和輸入：第一行：n（N<10000）第二行：n個整數(shù)（-3000，3000）。輸出：最大連續(xù)子序列的和。樣例：輸入：7-64-13

2-32輸出：8第25頁，課件共48頁，創(chuàng)作于2023年2月算法1：枚舉任意連續(xù)區(qū)間求和找最大值

readln(n);fori:=1tondoread(a[i]);ans:=-30000000;fori:=1tondoforj:=itondobeginsum:=0;fork:=itojdosum:=sum+a[k];ifsum>ansthenans:=sum;end;writeln(ans);時間：O(n3)理想的算法：<=106第26頁，課件共48頁，創(chuàng)作于2023年2月算法2：算法1的優(yōu)化

readln(n);fori:=1tondoread(a[i]);ans:=-30000000;fori:=1tondobeginsum:=0;forj:=itondobeginsum:=sum+a[j];ifsum>ansthenans:=sum;end;end;writeln(ans);

時間：O(n2)第27頁，課件共48頁，創(chuàng)作于2023年2月算法1和算法2是把n個數(shù)看作獨(dú)立的沒有聯(lián)系的數(shù)來處理的。1、以a[i]為結(jié)束點(diǎn)和以a[i+1]為結(jié)束點(diǎn)的最大連續(xù)子序列有沒有聯(lián)系？有什么樣的聯(lián)系？2、f[i]：從第1項(xiàng)開始，以a[i]為終點(diǎn)（右邊界）的子序列的最大和。如果事先已經(jīng)求得了以a[i]為結(jié)束點(diǎn)的最大連續(xù)子序列和為f[i]，那么怎樣求以a[i+1]為結(jié)束點(diǎn)的最大連續(xù)子序列？-64-132-32第28頁，課件共48頁，創(chuàng)作于2023年2月算法3：a[i]:存儲序列；f[i]：從第1項(xiàng)開始，以a[i]為終點(diǎn)（右邊界）的子序列的最大和。f[i]=max{f[i-1]+a[i],a[i]}：即看f[i-1]的正負(fù)初始：f[1]=a[1]目標(biāo)：max{f[i]}1<=i<=nproceduredp;beginf[1]:=a[1];fori:=2tondof[i]:=max(f[i-1]+a[i],a[i]);ans:=f[1];fori:=2tondoiff[i]>ansthenans:=f[i];end;時間：O(n)第29頁，課件共48頁，創(chuàng)作于2023年2月在一個n×m的方格中，m為奇數(shù)，放置有n×m個數(shù)，如圖1643126034-56700260-1-236853400-27-17407-560-1341242人方格中間的下方有一人，此人可按照五個方向前進(jìn)但不能越出方格。如所示：

5取數(shù)n,m<=100,方格數(shù)[-100，100]第30頁，課件共48頁，創(chuàng)作于2023年2月樣例輸入：671643126034-56700260-1-236853400-27-17407-560-1341242樣例輸出：51第31頁，課件共48頁，創(chuàng)作于2023年2月f[i,j]:人走到（i，j）時得數(shù)的最大值。f[i,j]=max{f[i+1,j-2],f[i+1,j-1],f[i+1,j],f[i+1,j+1],f[i+1,j+2]}+a[i,j]第32頁，課件共48頁，創(chuàng)作于2023年2月

proceduredp;begink:=mdiv2+1;fori:=k-2tok+2dof[n,i]:=a[n,i];fori:=n-1downto1doforj:=max(1,k-2*i)tomin(k+2*i,m)dobeginf[i,j]:=-10001;fork:=-2to2doif(k+j>=1)and(k+j<=m)and(f[i+1,k+j]>f[i,j])thenf[i,j]:=f[i+1,k+j];f[i,j]:=f[i,j]+a[i,j];end;ans:=f[1,1];fori:=2tomdoiff[1,i]>ansthenans:=f[1,i];writeln(ans);end;第33頁，課件共48頁，創(chuàng)作于2023年2月6迷宮尋寶一個n行m列的迷宮（1<=n,m<=50），入口在左上角，規(guī)定只能向下或向右走。迷宮的某些地方藏有不同價值的寶藏，同時有存在一些障礙無法通過。求到達(dá)右下角出口時收集的寶藏的最大值。輸入：第一行n和m，n行m列：迷宮矩陣a[i,j]（-1：障礙）保證a[1,1]<>-1。輸出：最大值。樣例：輸入2：54213-11-1-1-12-120-13125-11-12輸出2：18輸入1：342-15051

3-16-18910輸出1：33第34頁，課件共48頁，創(chuàng)作于2023年2月i,ji,j+1i+1,ji-1,ji,j-1i,j第35頁，課件共48頁，創(chuàng)作于2023年2月分析：逐行掃描

a[i,j]保存第i行第j列的寶藏價值．

f[i,j]走到第i行第j列時所能收集的寶藏的最大價值．狀態(tài)轉(zhuǎn)移方程：

f[i,j]=max{f[i-1,j],f[i,j-1]}+a[i,j](1<=n,1<=m)

條件:a[i,j]<>-1時.

初始：f[1,1]=a[1,1];

目標(biāo)：f[n,m]第36頁，課件共48頁，創(chuàng)作于2023年2月functionmax(a,b:integer):integer;beginmax:=a;ifb>athenmax:=b;end;proceduredp;beginfillchar(f,sizeof(f),0);fori:=1tondoforj:=1tomdoifa[i,j]<>-1thenf[i,j]:=max(f[i-1,j],f[i,j-1])+a[i,j];end;？第37頁，課件共48頁，創(chuàng)作于2023年2月-1-120第38頁，課件共48頁，創(chuàng)作于2023年2月讀入數(shù)據(jù)的預(yù)處理：

ifa[i-1,j]=-1anda[i,j-1]=-1thena[i,j]=-1varf,a:array[0..maxn,0..maxm]ofinteger;{加邊界，減少判斷越界}

readln(n,m);fori:=0ton+1do{初始全是障礙}forj:=0tom+1doa[i,j]:=-1;a[0,1]:=0;{保證a[1,1]能到達(dá)}fori:=1tondoforj:=1tomdobeginread(a[i,j]);if(a[i,j-1]=-1)and(a[i-1,j]=-1)thena[i,j]:=-1;end;342-150513-16-18910第39頁，課件共48頁，創(chuàng)作于2023年2月某國為了防御敵國的導(dǎo)彈襲擊，發(fā)展出一種導(dǎo)彈攔截系統(tǒng)（能發(fā)射任意發(fā)炮彈）。但是這種導(dǎo)彈攔截系統(tǒng)有一個缺陷：雖然它的第一發(fā)炮彈能夠到達(dá)任意的高度，但是以后每一發(fā)炮彈都要求高于前一發(fā)的高度。某天，雷達(dá)捕捉到敵國的導(dǎo)彈來襲。由于該系統(tǒng)還在試用階段，所以只有一套系統(tǒng)，因此有可能不能攔截所有的導(dǎo)彈。

輸入敵國導(dǎo)彈依次飛來的高度（雷達(dá)給出的高度數(shù)據(jù)是不大于30000的正整數(shù)），計(jì)算這套系統(tǒng)最多能攔截多少導(dǎo)彈7、攔截導(dǎo)彈第40頁，課件共48頁，創(chuàng)作于2023年2月輸入:

第一行：n（<=1000），敵國導(dǎo)彈的數(shù)量。依次是敵國導(dǎo)彈的高度(<30000)。輸出：最多攔截敵國導(dǎo)彈的數(shù)量。樣例：輸入：8271910123輸出：4第41頁，課件共48頁，創(chuàng)作于2023年2月轉(zhuǎn)化：

求最長的遞增子序列