c++編程入門(mén)第五次課

五、動(dòng)態(tài)規(guī)劃王振昊五、動(dòng)態(tài)規(guī)劃動(dòng)態(tài)規(guī)劃程序設(shè)計(jì)是對(duì)解最優(yōu)化問(wèn)題的一種途徑、一種方法，而不是一種特殊算法。不象前面所述的搜索一樣，具有一個(gè)標(biāo)準(zhǔn)的數(shù)學(xué)表達(dá)式和明確清晰的解題方法。動(dòng)態(tài)規(guī)劃程序設(shè)計(jì)往往是針對(duì)一種最優(yōu)化問(wèn)題，由于各種問(wèn)題的性質(zhì)不同，確定最優(yōu)解的條件也互不相同，因而動(dòng)態(tài)規(guī)劃的設(shè)計(jì)方法對(duì)不同的問(wèn)題，有各具特色的解題方法，而不存在一種萬(wàn)能的動(dòng)態(tài)規(guī)劃算法，可以解決各類(lèi)最優(yōu)化問(wèn)題。因此同學(xué)們?cè)趯W(xué)習(xí)時(shí)，除了要對(duì)根本概念和方法正確理解外，必須具體問(wèn)題具體分析處理，以豐富的想象力去建立模型，用創(chuàng)造性的技巧去求解。五、動(dòng)態(tài)規(guī)劃5.1初談動(dòng)態(tài)規(guī)劃5.2背包問(wèn)題5.3線性動(dòng)歸5.4坐標(biāo)型動(dòng)歸5.1初談動(dòng)態(tài)規(guī)劃多階段決策過(guò)程的最優(yōu)化問(wèn)題在現(xiàn)實(shí)生活中，有一類(lèi)活動(dòng)的過(guò)程，由于它的特殊性，可將過(guò)程分成假設(shè)干個(gè)互相聯(lián)系的階段，在它的每一階段都需要作出決策，從而使整個(gè)過(guò)程到達(dá)最好的活動(dòng)效果。當(dāng)然，各個(gè)階段決策的選取不是任意確定的，它依賴(lài)于當(dāng)前面臨的狀態(tài)，又影響以后的開(kāi)展，當(dāng)各個(gè)階段決策確定后，就組成一個(gè)決策序列，因而也就確定了整個(gè)過(guò)程的一條活動(dòng)路線，這種把一個(gè)問(wèn)題看作是一個(gè)前后關(guān)聯(lián)具有鏈狀結(jié)構(gòu)的多階段過(guò)程就稱(chēng)為多階段決策過(guò)程，這種問(wèn)題就稱(chēng)為多階段決策問(wèn)題。如以下圖所示：多階段決策過(guò)程，是指這樣的一類(lèi)特殊的活動(dòng)過(guò)程，問(wèn)題可以按時(shí)間順序分解成假設(shè)干相互聯(lián)系的階段，在每一個(gè)階段都要做出決策，全部過(guò)程的決策是一個(gè)決策序列。5.1初談動(dòng)態(tài)規(guī)劃

一道小學(xué)奧數(shù)題：由A走到B的路徑個(gè)數(shù)？AB5.1初談動(dòng)態(tài)規(guī)劃5.1初談動(dòng)態(tài)規(guī)劃最短路徑問(wèn)題。以下圖給出了一個(gè)地圖，地圖中的每個(gè)頂點(diǎn)代表一個(gè)城市，兩個(gè)城市間的一條連線代表道路，連線上的數(shù)值代表道路的長(zhǎng)度?，F(xiàn)在想從城市A到達(dá)城市E，怎樣走路程最短？最短路程的長(zhǎng)度是多少？5.1初談動(dòng)態(tài)規(guī)劃把A到E的全過(guò)程分成四個(gè)階段，用K表示階段變量，第1階段有一個(gè)初始狀態(tài)A，有兩條可供選擇的支路A-B1、A-B2；第2階段有兩個(gè)初始狀態(tài)B1、B2，B1有三條可供選擇的支路，B2有兩條可供選擇的支路……。用DK〔XI，X+1J〕表示在第K階段由初始狀態(tài)XI到下階段的初始狀態(tài)X+1J的路徑距離，F(xiàn)K〔XI〕表示從第K階段的XI到終點(diǎn)E的最短距離，利用倒推的方法，求解A到E的最短距離。具體計(jì)算過(guò)程如下：S1：K=4有F4〔D1〕=3，F(xiàn)4〔D2〕=4，F(xiàn)4〔D3〕=3；S2：K=3有F3〔C1〕=MIN{D3〔C1，D1〕+F4〔D1〕，D3〔C1，D2〕+F4〔D2〕}=MIN{5+3，6+4}=8F3〔C2〕=D3〔C2，D1〕+F4〔D1〕=5+3=8F3〔C3〕=D3〔C3，D3〕+F4〔D3〕=8+3=11F3〔C4〕=D3〔C4，D3〕+F4〔D3〕=3+3=6S3：K=2有F2〔B1〕=MIN{D2〔B1，C1〕+F3〔C1〕，D2〔B1，C2〕+F3〔C2〕，D2〔B1，C3〕+F3(C3)}=MIN{1+8,6+8,3+11}=9F2〔B2〕=MIN{D2〔B2，C2〕+F3〔C2〕，D2〔B2，C4〕+F3〔C4〕}=MIN{8+8，4+6}=10S4：K=1有F1〔A〕=MIN{D1〔A，B1〕+F2〔B1〕，D1〔A，B2〕+F2〔B2〕}=MIN{5+9，3+10}=135.1初談動(dòng)態(tài)規(guī)劃因此由A點(diǎn)到E點(diǎn)的全過(guò)程最短路徑為A→B2→C4→D3→E；最短路程長(zhǎng)度為13。從以上過(guò)程可以看出，每個(gè)階段中，都求出本階段的各個(gè)初始狀態(tài)到終點(diǎn)E的最短距離，當(dāng)逆序倒推到過(guò)程起點(diǎn)A時(shí)，便得到了全過(guò)程的最短路徑和最短距離。在上例的多階段決策問(wèn)題中，各個(gè)階段采取的決策，一般來(lái)說(shuō)是與階段有關(guān)的，決策依賴(lài)于當(dāng)前狀態(tài)，又隨即引起狀態(tài)的轉(zhuǎn)移，一個(gè)決策序列就是在變化的狀態(tài)中產(chǎn)生出來(lái)的，故有“動(dòng)態(tài)”的含義，我們稱(chēng)這種解決多階段決策最優(yōu)化的過(guò)程為動(dòng)態(tài)規(guī)劃程序設(shè)計(jì)方法。5.1初談動(dòng)態(tài)規(guī)劃現(xiàn)在我們來(lái)介紹動(dòng)態(tài)規(guī)劃的根本概念。1.階段和階段變量：用動(dòng)態(tài)規(guī)劃求解一個(gè)問(wèn)題時(shí)，需要將問(wèn)題的全過(guò)程恰當(dāng)?shù)胤殖杉僭O(shè)干個(gè)相互聯(lián)系的階段，以便按一定的次序去求解。描述階段的變量稱(chēng)為階段變量，通常用K表示，階段的劃分一般是根據(jù)時(shí)間和空間的自然特征來(lái)劃分，同時(shí)階段的劃分要便于把問(wèn)題轉(zhuǎn)化成多階段決策過(guò)程，如例題1中，可將其劃分成4個(gè)階段，即K=1，2，3，4。2.狀態(tài)和狀態(tài)變量：某一階段的出發(fā)位置稱(chēng)為狀態(tài)，通常一個(gè)階段包含假設(shè)干狀態(tài)。一般地，狀態(tài)可由變量來(lái)描述，用來(lái)描述狀態(tài)的變量稱(chēng)為狀態(tài)變量。如例題1中，C3是一個(gè)狀態(tài)變量。3.決策、決策變量和決策允許集合：在對(duì)問(wèn)題的處理中作出的每種選擇性的行動(dòng)就是決策。即從該階段的每一個(gè)狀態(tài)出發(fā)，通過(guò)一次選擇性的行動(dòng)轉(zhuǎn)移至下一階段的相應(yīng)狀態(tài)。一個(gè)實(shí)際問(wèn)題可能要有屢次決策和多個(gè)決策點(diǎn)，在每一個(gè)階段的每一個(gè)狀態(tài)中都需要有一次決策，決策也可以用變量來(lái)描述，稱(chēng)這種變量為決策變量。在實(shí)際問(wèn)題中，決策變量的取值往往限制在某一個(gè)范圍之內(nèi)，此范圍稱(chēng)為允許決策集合。如例題1中，F(xiàn)3〔C3〕就是一個(gè)決策變量。4．策略和最優(yōu)策略：所有階段依次排列構(gòu)成問(wèn)題的全過(guò)程。全過(guò)程中各階段決策變量所組成的有序總體稱(chēng)為策略。在實(shí)際問(wèn)題中，從決策允許集合中找出最優(yōu)效果的策略成為最優(yōu)策略。5.狀態(tài)轉(zhuǎn)移方程前一階段的終點(diǎn)就是后一階段的起點(diǎn)，對(duì)前一階段的狀態(tài)作出某種決策，產(chǎn)生后一階段的狀態(tài)，這種關(guān)系描述了由k階段到k+1階段狀態(tài)的演變規(guī)律，稱(chēng)為狀態(tài)轉(zhuǎn)移方程。5.1初談動(dòng)態(tài)規(guī)劃最優(yōu)化原理與無(wú)后效性上面已經(jīng)介紹了動(dòng)態(tài)規(guī)劃模型的根本組成，現(xiàn)在需要解決的問(wèn)題是：什么樣的“多階段決策問(wèn)題”才可以采用動(dòng)態(tài)規(guī)劃的方法求解。一般來(lái)說(shuō)，能夠采用動(dòng)態(tài)規(guī)劃方法求解的問(wèn)題，必須滿(mǎn)足最優(yōu)化原理和無(wú)后效性原那么：1、動(dòng)態(tài)規(guī)劃的最優(yōu)化原理。作為整個(gè)過(guò)程的最優(yōu)策略具有：無(wú)論過(guò)去的狀態(tài)和決策如何，對(duì)前面的決策所形成的狀態(tài)而言，余下的諸決策必須構(gòu)成最優(yōu)策略的性質(zhì)。也可以通俗地理解為子問(wèn)題的局部最優(yōu)將導(dǎo)致整個(gè)問(wèn)題的全局最優(yōu)，即問(wèn)題具有最優(yōu)子結(jié)構(gòu)的性質(zhì)，也就是說(shuō)一個(gè)問(wèn)題的最優(yōu)解只取決于其子問(wèn)題的最優(yōu)解，而非最優(yōu)解對(duì)問(wèn)題的求解沒(méi)有影響。在例題1最短路徑問(wèn)題中，A到E的最優(yōu)路徑上的任一點(diǎn)到終點(diǎn)E的路徑，也必然是該點(diǎn)到終點(diǎn)E的一條最優(yōu)路徑，即整體優(yōu)化可以分解為假設(shè)干個(gè)局部?jī)?yōu)化。2、動(dòng)態(tài)規(guī)劃的無(wú)后效性原那么。所謂無(wú)后效性原那么，指的是這樣一種性質(zhì)：某階段的狀態(tài)一旦確定，那么此后過(guò)程的演變不再受此前各狀態(tài)及決策的影響。也就是說(shuō)，“未來(lái)與過(guò)去無(wú)關(guān)”，當(dāng)前的狀態(tài)是此前歷史的一個(gè)完整的總結(jié)，此前的歷史只能通過(guò)當(dāng)前的狀態(tài)去影響過(guò)程未來(lái)的演變。在例題1最短路徑問(wèn)題中，問(wèn)題被劃分成各個(gè)階段之后，階段K中的狀態(tài)只能由階段K+1中的狀態(tài)通過(guò)狀態(tài)轉(zhuǎn)移方程得來(lái)，與其它狀態(tài)沒(méi)有關(guān)系，特別與未發(fā)生的狀態(tài)沒(méi)有關(guān)系，例如從Ci到E的最短路徑，只與Ci的位置有關(guān)，它是由Di中的狀態(tài)通過(guò)狀態(tài)轉(zhuǎn)移方程得來(lái)，與E狀態(tài)，特別是A到Ci的路徑選擇無(wú)關(guān)，這就是無(wú)后效性。由此可見(jiàn)，對(duì)于不能劃分階段的問(wèn)題，不能運(yùn)用動(dòng)態(tài)規(guī)劃來(lái)解；對(duì)于能劃分階段，但不符合最優(yōu)化原理的，也不能用動(dòng)態(tài)規(guī)劃來(lái)解；既能劃分階段，又符合最優(yōu)化原理的，但不具備無(wú)后效性原那么，還是不能用動(dòng)態(tài)規(guī)劃來(lái)解；誤用動(dòng)態(tài)規(guī)劃程序設(shè)計(jì)方法求解會(huì)導(dǎo)致錯(cuò)誤的結(jié)果。5.1初談動(dòng)態(tài)規(guī)劃動(dòng)態(tài)規(guī)劃所處理的問(wèn)題是一個(gè)多階段決策問(wèn)題，一般由初始狀態(tài)開(kāi)始，通過(guò)對(duì)中間階段決策的選擇，到達(dá)結(jié)束狀態(tài)；或倒過(guò)來(lái)，從結(jié)束狀態(tài)開(kāi)始，通過(guò)對(duì)中間階段決策的選擇，到達(dá)初始狀態(tài)。這些決策形成一個(gè)決策序列，同時(shí)確定了完成整個(gè)過(guò)程的一條活動(dòng)路線，通常是求最優(yōu)活動(dòng)路線。動(dòng)態(tài)規(guī)劃的設(shè)計(jì)都有著一定的模式，一般要經(jīng)歷以下幾個(gè)步驟：1、劃分階段按照問(wèn)題的時(shí)間或空間特征，把問(wèn)題劃分為假設(shè)干個(gè)階段。在劃分階段時(shí)，注意劃分后的階段一定是有序的或者是可排序的，否那么問(wèn)題就無(wú)法求解。2、確定狀態(tài)和狀態(tài)變量將問(wèn)題開(kāi)展到各個(gè)階段時(shí)所處于的各種客觀情況用不同的狀態(tài)表示出來(lái)。當(dāng)然，狀態(tài)的選擇要滿(mǎn)足無(wú)后效性。3、確定決策并寫(xiě)出狀態(tài)轉(zhuǎn)移方程因?yàn)闆Q策和狀態(tài)轉(zhuǎn)移有著天然的聯(lián)系，狀態(tài)轉(zhuǎn)移就是根據(jù)上一階段的狀態(tài)和決策來(lái)導(dǎo)出本階段的狀態(tài)。所以如果確定了決策，狀態(tài)轉(zhuǎn)移方程也就可以寫(xiě)出。但事實(shí)上常常是反過(guò)來(lái)做，根據(jù)相鄰兩段的各個(gè)狀態(tài)之間的關(guān)系來(lái)確定決策。4、尋找邊界條件給出的狀態(tài)轉(zhuǎn)移方程是一個(gè)遞推式，需要一個(gè)遞推的終止條件或邊界條件。5.1初談動(dòng)態(tài)規(guī)劃#include<iostream>#include<cstring>usingnamespacestd;intmain(){longd[5][5][5],f[10][10];memset(d,42,sizeof(d));//有些路徑是不通的,賦值為較大值，用于判斷d[1][1][1]=5;d[1][1][2]=3;d[2][1][1]=1;//以下給可通路徑賦正常值d[2][1][2]=6;d[2][1][3]=3;d[2][2][2]=8d[2][2][4]=4;d[3][1][1]=5;d[3][1][2]=6;d[3][2][1]=5;d[3][3][3]=8;d[3][4][3]=3;d[4][1][1]=3;d[4][2][1]=4;d[4][3][1]=3;for(inti=0;i<=9;++i)for(intj=0;j<=9;++j)f[i][j]=10000000;f[5][1]=0;for(inti=4;i>=1;--i)for(intj=1;j<=4;++j)for(intk=1;k<=4;++k)if(f[i][j]>d[i][j][k]+f[i+1][k])//即使走非法路徑，也不影響答案f[i][j]=d[i][j][k]+f[i+1][k];cout<<f[1][1]<<endl;}5.1初談動(dòng)態(tài)規(guī)劃動(dòng)態(tài)規(guī)劃的兩種實(shí)現(xiàn)方式：1.遞推實(shí)現(xiàn)方式2.遞歸實(shí)現(xiàn)方式〔記憶化搜索〕5.1初談動(dòng)態(tài)規(guī)劃數(shù)字三角型〔IOI94〕有形如下圖的數(shù)字三角形，從頂部出發(fā)，在每一結(jié)點(diǎn)可以選擇向左走或是向右走，一起走到底層，要求找出一條路徑，使路徑上的值最大?！窘夥ㄒ弧俊材嫱品ā场舅惴ǚ治觥竣儇澬姆ㄍ貌坏阶顑?yōu)解：此題假設(shè)采用貪心法那么：13-11-12-14-13，其和為63,但存在另一條路：13-8-26-15-24，其和為86。貪心法問(wèn)題所在：眼光短淺。②動(dòng)態(tài)規(guī)劃求解：動(dòng)態(tài)規(guī)劃求解問(wèn)題的過(guò)程歸納為：自頂向下的分析，自底向上計(jì)算。其根本方法是：劃分階段：按三角形的行，劃分階段，假設(shè)有n行，那么有n-1個(gè)階段。A．從根結(jié)點(diǎn)13出發(fā)，選取它的兩個(gè)方向中的一條支路，當(dāng)?shù)降箶?shù)第二層時(shí)，每個(gè)結(jié)點(diǎn)其后繼僅有兩個(gè)結(jié)點(diǎn)，可以直接比較，選擇最大值為前進(jìn)方向，從而求得從根結(jié)點(diǎn)開(kāi)始到底端的最大路徑。B．自底向上計(jì)算：〔給出遞推式和終止條件〕①?gòu)牡讓娱_(kāi)始，本身數(shù)即為最大數(shù)；②倒數(shù)第二層的計(jì)算，取決于底層的數(shù)據(jù)：12+6=18，13+14=27，24+15=39，24+8=32；③倒數(shù)第三層的計(jì)算，取決于底二層計(jì)算的數(shù)據(jù)：27+12=39，39+7=46，39+26=65④倒數(shù)第四層的計(jì)算，取決于底三層計(jì)算的數(shù)據(jù)：46+11=57，65+8=73⑤最后的路徑：13——8——26——15——24C．?dāng)?shù)據(jù)結(jié)構(gòu)及算法設(shè)計(jì)①圖形轉(zhuǎn)化：直角三角形，便于搜索：向下、向右②用三維數(shù)組表示數(shù)塔：a[x,y,1]表示行、列及結(jié)點(diǎn)本身數(shù)據(jù),a[x,y,2]能夠取得最大值,a[x,y,3]表示前進(jìn)的方向——0向下，1向右；③算法：數(shù)組初始化，輸入每個(gè)結(jié)點(diǎn)值及初始的最大路徑、前進(jìn)方向?yàn)?；從倒數(shù)第二層開(kāi)始向上一層求最大路徑，共循環(huán)N-1次；從頂向下，輸出路徑：究竟向下還是向右取決于列的值，假設(shè)列的值比原先多1那么向右，否那么向下。

參考程序#include<iostream>#include<cstring>usingnamespacestd;intmain(){ intn,x,y; inta[51][51][3]; cout<<"pleaseinputthenumberofrows:"; cin>>n; memset(a,0,sizeof(0)); for(x=1;x<=n;x++)//輸入數(shù)塔的初始值 for(y=1;y<=x;y++) { cin>>a[x][y][1]; a[x][y][2]=a[x][y][1]; a[x][y][3]=0;//路徑走向，默認(rèn)向下 }for(x=n-1;x>=1;x--)for(y=1;y<=x;y++)if(a[x+1][y][2]>a[x+1][y+1][2])//選擇路徑，保存最大路徑值{a[x][y][2]=a[x][y][2]+a[x+1][y][2];a[x][y][3]=0;}else{a[x][y][2]=a[x][y][2]+a[x+1][y+1][2];a[x][y][3]=1;}cout<<"max="<<a[1][1][2]<<endl;//輸出數(shù)塔最大值y=1;for(x=1;x<=n-1;x++)//輸出數(shù)塔最大值的路徑{cout<<a[x][y][1]<<"->";y=y+a[x][y][3];//下一行的列數(shù)}cout<<a[n][y][1]<<endl;}輸入：5//數(shù)塔層數(shù)1311812726614158127132411輸出結(jié)果：

max=8613->8->26->15->245.1初談動(dòng)態(tài)規(guī)劃【解法二】〔順推法〕【算法分析】此題貪心法往往得不到最優(yōu)解，例如13-11-12-14-13其路徑的值為63，但這不是最優(yōu)解。窮舉搜索往往是不可能的，當(dāng)層數(shù)N=100時(shí)，路徑條數(shù)P=299這是一個(gè)非常大的數(shù)，即使用世界上最快的電子計(jì)算機(jī)，也不能在規(guī)定時(shí)間內(nèi)計(jì)算出來(lái)。對(duì)這道題唯一正確的方法是動(dòng)態(tài)規(guī)劃。如果得到一條由頂?shù)降椎哪程幍囊粭l最正確路徑，那么對(duì)于該路徑上的每一個(gè)中間點(diǎn)來(lái)說(shuō)，由頂點(diǎn)至該中間點(diǎn)的路徑所經(jīng)過(guò)的數(shù)字和也為最大。因此此題是一個(gè)典型的多階段決策最優(yōu)化問(wèn)題。在此題中僅要求輸出最優(yōu)解，為此我們?cè)O(shè)置了數(shù)組A[i,j]保存三角形數(shù)塔，B[i,j]保存狀態(tài)值，按從上往下方式進(jìn)行求解。階段i：以層數(shù)來(lái)劃分階段，由從上往下方式計(jì)算；因此可通過(guò)第一重循環(huán): for(inti=1;i<=n;i++)枚舉每一階段；狀態(tài)B[i][j]：由于每個(gè)階段中有多個(gè)狀態(tài)，因此可通過(guò)第二重循環(huán): for(intj=1;j<=i;j++)求出每個(gè)階段的每個(gè)狀態(tài)的最優(yōu)解B[i][j]；決策：每個(gè)狀態(tài)最多由上一層的兩個(gè)結(jié)點(diǎn)連接過(guò)來(lái)，因此不需要做循環(huán)。

【參考程序】#include<iostream>#include<cstring>usingnamespacestd;intmain(){ intn,i,j,a[200][200],b[200][200],max;

cin>>n;memset(a,0,sizeof(a));memset(b,0,sizeof(b));for(i=1;i<=n;++i) for(j=1;j<=i;++jj) { cin>>a[i][j]; b[i][j]=a[i][j]; }

for(i=2;i<=n;++i)//選擇路徑，保存最大路徑值for(j=1;j<=i;++j)if(b[i-1][j-1]>b[i-1][j])b[i][j]=b[i][j]+b[i-1][j-1];elseb[i][j]=b[i][j]+b[i-1][j];max=0;for(j=1;j<=n;++j)if(b[n][j]>max)//在第n行中找出數(shù)塔最大值max=b[n][j];cout<<"Max="<<max<<endl;//輸出數(shù)塔最大值}5.2背包問(wèn)題一、01背包問(wèn)題有N件物品;第i件物品Wi公斤;第i件物品價(jià)值Ci元;現(xiàn)有一輛載重M公斤的卡車(chē);問(wèn)選取裝載哪些物品，使得卡車(chē)運(yùn)送的總價(jià)值最大？5.2背包問(wèn)題這是最根底的背包問(wèn)題，特點(diǎn)是：每種物品僅有一件，可以選擇放或不放。用子問(wèn)題定義狀態(tài)：即f[i][v]表示前i件物品(局部或全部)恰放入一個(gè)容量為v的背包可以獲得的最大價(jià)值。那么其狀態(tài)轉(zhuǎn)移方程便是：f[i][v]=max{f[i-1][v],f[i-1][v-w[i]]+c[i]}。這個(gè)方程非常重要，根本上所有跟背包相關(guān)的問(wèn)題的方程都是由它衍生出來(lái)的。所以有必要將它詳細(xì)解釋一下：“將前i件物品放入容量為v的背包中”這個(gè)子問(wèn)題，假設(shè)只考慮第i件物品的策略〔放或不放〕，那么就可以轉(zhuǎn)化為一個(gè)只牽扯前i-1件物品的問(wèn)題。如果不放第i件物品，那么問(wèn)題就轉(zhuǎn)化為“前i-1件物品放入容量為v的背包中”；如果放第i件物品，那么問(wèn)題就轉(zhuǎn)化為“前i-1件物品放入剩下的容量為v-w[i]的背包中”，此時(shí)能獲得的最大價(jià)值就是f[i-1][v-w[i]]再加上通過(guò)放入第i件物品獲得的價(jià)值c[i]。

5.2背包問(wèn)題注意f[i][v]有意義當(dāng)且僅當(dāng)存在一個(gè)前i件物品的子集，其費(fèi)用總和為v。所以按照這個(gè)方程遞推完畢后，最終的答案并不一定是f[N][V]，而是f[N][0..V]的最大值。如果將狀態(tài)的定義中的“恰”字去掉，在轉(zhuǎn)移方程中就要再參加一項(xiàng)f[i-1][v]，這樣就可以保證f[N][V]就是最后的答案。但是假設(shè)將所有f[i][j]的初始值都賦為0，你會(huì)發(fā)現(xiàn)f[n][v]也會(huì)是最后的答案。為什么呢？因?yàn)檫@樣你默認(rèn)了最開(kāi)始f[i][j]是有意義的，只是價(jià)值為0，就看作是無(wú)物品放的背包價(jià)值都為0，所以對(duì)最終價(jià)值無(wú)影響，這樣初始化后的狀態(tài)表示就可以把“恰”字去掉。5.2背包問(wèn)題優(yōu)化空間復(fù)雜度以上方法的時(shí)間和空間復(fù)雜度均為O(N*V)，其中時(shí)間復(fù)雜度根本已經(jīng)不能再優(yōu)化了，但空間復(fù)雜度卻可以?xún)?yōu)化到O(V)。先考慮上面講的根本思路如何實(shí)現(xiàn)，肯定是有一個(gè)主循環(huán)i=1..N，每次算出來(lái)二維數(shù)組f[i][0..V]的所有值。那么，如果只用一個(gè)數(shù)組f[0..V]，能不能保證第i次循環(huán)結(jié)束后f[v]中表示的就是我們定義的狀態(tài)f[i][v]呢？f[i][v]是由f[i-1][v]和f[i-1][v-w[i]]兩個(gè)子問(wèn)題遞推而來(lái)，能否保證在推f[i][v]時(shí)〔也即在第i次主循環(huán)中推f[v]時(shí)〕能夠得到f[i-1][v]和f[i-1][v-w[i]]的值呢？事實(shí)上，這要求在每次主循環(huán)中我們以v=V..0的逆序推f[v]，這樣才能保證推f[v]時(shí)f[v-w[i]]保存的是狀態(tài)f[i-1][v-w[i]]的值。偽代碼如下：fori=1..Nforv=V..0f[v]=max{f[v],f[v-w[i]]+c[i]};其中f[v]=max{f[v],f[v-w[i]]+c[i]}相當(dāng)于轉(zhuǎn)移方程f[i][v]=max{f[i-1][v],f[i-1][v-w[i]]+c[i]}，因?yàn)楝F(xiàn)在的f[v-w[i]]就相當(dāng)于原來(lái)的f[i-1][v-w[i]]。如果將v的循環(huán)順序從上面的逆序改成順序的話(huà)，那么那么成了f[i][v]由f[i][v-w[i]]推知，與此題意不符，但它卻是另一個(gè)重要的完全背包問(wèn)題最簡(jiǎn)捷的解決方案，故學(xué)習(xí)只用一維數(shù)組解01背包問(wèn)題是十分必要的。5.2背包問(wèn)題采藥〔noip05〕描述辰辰是個(gè)天資聰穎的孩子，他的夢(mèng)想是成為世界上最偉大的醫(yī)師。為此，他想拜附近最有威望的醫(yī)師為師。醫(yī)師為了判斷他的資質(zhì)，給他出了一個(gè)難題。醫(yī)師把他帶到一個(gè)到處都是草藥的山洞里對(duì)他說(shuō)：“孩子，這個(gè)山洞里有一些不同的草藥，采每一株都需要一些時(shí)間，每一株也有它自身的價(jià)值。我會(huì)給你一段時(shí)間，在這段時(shí)間里，你可以采到一些草藥。如果你是一個(gè)聰明的孩子，你應(yīng)該可以讓采到的草藥的總價(jià)值最大?！?/p>

如果你是辰辰，你能完成這個(gè)任務(wù)嗎？5.2背包問(wèn)題輸入格式輸入文件medic.in的第一行有兩個(gè)整數(shù)T〔1

<=

T

<=

1000〕和M〔1

<=

M

<=

100〕，用一個(gè)空格隔開(kāi)，T代表總共能夠用來(lái)采藥的時(shí)間，M代表山洞里的草藥的數(shù)目。接下來(lái)的M行每行包括兩個(gè)在1到100之間〔包括1和100〕的整數(shù)，分別表示采摘某株草藥的時(shí)間和這株草藥的價(jià)值。輸出格式輸出文件medic.out包括一行，這一行只包含一個(gè)整數(shù)，表示在規(guī)定的時(shí)間內(nèi)，可以采到的草藥的最大總價(jià)值。測(cè)試樣例1輸入703

71100

691

12輸出3備注對(duì)于30%的數(shù)據(jù)，M

<=

10；對(duì)于全部的數(shù)據(jù)，M

<=

100。5.2背包問(wèn)題#include<iostream>#include<cstring>usingnamespacestd;intmain(){ intt,m,i,j,c[101],w[101],f[10001]; cin>>t>>m; memset(f,0,sizeof(f)); for(i=0;i<m;++i) cin>>c[i]>>w[i]; for(i=0;i<m;++i) for(j=t;j>=c[i];--j) f[j]=(f[j]>f[j-c[i]]+w[i])?f[j]:f[j-c[i]]+w[i]; cout<<f[t]<<endl; return0;}5.2背包問(wèn)題二、滿(mǎn)01背包有N件物品;第i件物品Wi公斤;第i件物品價(jià)值Ci元;現(xiàn)有一輛載重M公斤的卡車(chē);問(wèn)選取裝載哪些物品，使得卡車(chē)開(kāi)車(chē)正好裝滿(mǎn)時(shí)，運(yùn)送的總價(jià)值最大？ 假設(shè)無(wú)法裝滿(mǎn)卡車(chē)，那么輸出無(wú)解。5.2背包問(wèn)題設(shè)F(i,j)表示前i件物品背包為j的最大效益，那么有1<=i<=N,0<=j<=N初值：F(0,j)=0，F(xiàn)(1,j)=-∞F(N,M)即答案顯然時(shí)間復(fù)雜度為O(NM)5.2背包問(wèn)題三、帶條件的背包問(wèn)題〔1〕有N件物品;第i件物品Wi公斤;第i件物品價(jià)值Ci元;第i件物品可能帶0~2個(gè)附件；假設(shè)裝載附件，必須裝載主件，反之沒(méi)有約束；現(xiàn)有一輛載重M公斤的卡車(chē);問(wèn)選取裝載哪些物品，使得卡車(chē)運(yùn)送的總價(jià)值最大？5.2背包問(wèn)題假設(shè)只有主件的情況，顯然與經(jīng)典背包問(wèn)題完全相同！現(xiàn)在每個(gè)物品有附件，我們可以分成4種方案僅裝載主件裝載主件+第1個(gè)附件裝載主件+第2個(gè)附件裝載主件+2個(gè)附件由于上述4種并列，這是幾種不同的決策同時(shí)規(guī)劃即可5.2背包問(wèn)題設(shè)F(i,j)表示前i件物品背包為j的最優(yōu)解，那么有，1<=i<=N,0<=j<=M時(shí)間復(fù)雜度O(NM)〔開(kāi)心的金明〕5.2背包問(wèn)題四、多層背包問(wèn)題有N件物品;第i件物品Wi公斤;第i件物品價(jià)值Ci元;現(xiàn)有一輛載重M公斤的卡車(chē);第i件物品限制最多只能取Xi個(gè)；問(wèn)選取裝載哪些物品，使得卡車(chē)運(yùn)送的總價(jià)值最大？5.2背包問(wèn)題我們可以類(lèi)似01背包問(wèn)題，將第i種物品拆分成x[i]個(gè)，這樣每個(gè)物品只有1件了,如以下圖:然后對(duì)所有的物品采用動(dòng)態(tài)規(guī)劃即可。F(i,j)=max{f(i-1,j-k*w[i])+k*c[i]}0<=k*w[i]<=j5.2背包問(wèn)題五、完全背包問(wèn)題有N件物品;第i件物品Wi公斤;第i件物品價(jià)值Ci元;現(xiàn)有一輛載重M公斤的卡車(chē);每次可以選取某種物品的任意多件裝載；問(wèn)選取裝載哪些物品，使得卡車(chē)運(yùn)送的總價(jià)值最大？5.2背包問(wèn)題類(lèi)似多層背包問(wèn)題將每個(gè)物品展開(kāi)成X[i]=m/w[i]個(gè)，然后對(duì)所有的物品采用動(dòng)態(tài)規(guī)劃即可。假設(shè)兩件物品i、j滿(mǎn)足c[i]<=c[j]且w[i]>=w[j],那么將物品i去掉,不用考慮。這個(gè)優(yōu)化的正確性顯然：任何情況下都可將價(jià)值小費(fèi)用高的j換成物美價(jià)廉的i,得到至少不會(huì)更差的方案。由于每種物品有選和不選兩種情況，可以將每種物品的2k個(gè)當(dāng)成一個(gè)整體考慮。這樣對(duì)于某種物品要選取多個(gè)，都可以由假設(shè)干個(gè)2k個(gè)物品進(jìn)行組合(即2進(jìn)制數(shù))。例如第i種物品要選10個(gè)，那么10=23+21。這樣第i種物品的個(gè)數(shù)為k=㏒2(m/wi)物品，是一個(gè)很大的改進(jìn)。進(jìn)一步,在計(jì)算k時(shí),K=㏒2(j/wi),j為當(dāng)前背包剩余空間。5.2背包問(wèn)題fori:=1tondo//動(dòng)態(tài)規(guī)劃，遞推求f forj:=mdownto1do begin ifj>=w[i]then//背包容量夠大 f[i,j]:=max(f[i-1,j-w[i]]+c[i],f[i-1,j]) else//背包容量缺乏f[i,j]:=f[i-1,j]; end;在這里為了使得每個(gè)物品只取1個(gè)或不取,采用了每次取j都是與i-1進(jìn)行比較，實(shí)際上保存了每1步取不同j的值5.2背包問(wèn)題事實(shí)上，我們只關(guān)心剩余背包的最大值，也就是僅僅關(guān)心f(j),因此，在對(duì)f(j)更新時(shí)，只要背包容量可以，那么可以反復(fù)更新。程序如下： fori:=1tondo//動(dòng)態(tài)規(guī)劃，遞推求f forj:=0tomdo begin ifj>=w[i]then//背包容量夠大

f[j]:=max(f[j-w[i]]+c[i],f[j]) end;5.2背包問(wèn)題對(duì)于背包問(wèn)題，我們可以看出，問(wèn)題描述必須有一個(gè)根本要素：資源，有時(shí)這種資源可能是金錢(qián)、空間或者時(shí)間，問(wèn)題就是要對(duì)這些資源如何分配，一種根本的想法是將資源應(yīng)用于前i個(gè)階段，然后考慮第i個(gè)階段和前i-1個(gè)階段之間的關(guān)系。設(shè)前i個(gè)點(diǎn)的消耗j的資源得到的最優(yōu)值，研究前i-1個(gè)點(diǎn)消耗的資源的最優(yōu)值，利用第i個(gè)點(diǎn)決策轉(zhuǎn)移，如以下圖。狀態(tài)轉(zhuǎn)移方程一般可寫(xiě)成:fi(j)=min{fi-1(k)+ui(j,k)}5.3線性動(dòng)歸線性動(dòng)歸即為常規(guī)的動(dòng)歸題目，狀態(tài)轉(zhuǎn)移為線性求最長(zhǎng)不下降序列㈠問(wèn)題描述：設(shè)有由n個(gè)不相同的整數(shù)組成的數(shù)列，記為:b(1)、b(2)、……、b(n)且b(i)<>b(j)

(i<>j)，假設(shè)存在i1<i2<i3<…<ie且有b(i1)<b(i2)<…<b(ie)那么稱(chēng)為長(zhǎng)度為e的不下降序列。程序要求，當(dāng)原數(shù)列出之后，求出最長(zhǎng)的不下降序列。例如13，7，9，16，38，24，37，18，44，19，21，22，63，15。例中13，16，18，19，21，22，63就是一個(gè)長(zhǎng)度為7的不下降序列，同時(shí)也有7，9，16，18，19，21，22，63長(zhǎng)度為8的不下降序列。㈡算法分析：根據(jù)動(dòng)態(tài)規(guī)劃的原理，由后往前進(jìn)行搜索(當(dāng)然從前往后也一樣)。1·對(duì)b(n)來(lái)說(shuō)，由于它是最后一個(gè)數(shù)，所以當(dāng)從b(n)開(kāi)始查找時(shí)，只存在長(zhǎng)度為1的不下降序列；2·假設(shè)從b(n-1)開(kāi)始查找，那么存在下面的兩種可能性：①假設(shè)b(n-1)<b(n)那么存在長(zhǎng)度為2的不下降序列b(n-1)，b(n)。②假設(shè)b(n-1)>b(n)那么存在長(zhǎng)度為1的不下降序列b(n-1)或b(n)。3·一般假設(shè)從b(i)開(kāi)始，此時(shí)最長(zhǎng)不下降序列應(yīng)該按以下方法求出:在b(i+1),b(i+2),…,b(n)中，找出一個(gè)比b(i)大的且最長(zhǎng)的不下降序列，作為它的后繼。㈢數(shù)據(jù)結(jié)構(gòu)：為算法上的需要，定義一個(gè)整數(shù)類(lèi)型二維數(shù)組b(N,3)1·b(I,1)表示第I個(gè)數(shù)的數(shù)值本身；2·b(I,2)表示從I位置到達(dá)N的最長(zhǎng)不下降序列長(zhǎng)度

3·b(I,3)表示從I位置開(kāi)始最長(zhǎng)不下降序列的下一個(gè)位置，假設(shè)b[I,3]=0那么表示后面沒(méi)有連接項(xiàng)。㈣求解過(guò)程：①?gòu)牡箶?shù)第二項(xiàng)開(kāi)始計(jì)算，后面僅有1項(xiàng)，比較一次，因63>15，不符合要求，長(zhǎng)度仍為1。②從倒數(shù)第三項(xiàng)開(kāi)始其后有2項(xiàng)，需做兩次比較，得到目前最長(zhǎng)的不下降序列為2，如下表：11121314……11121314226315……21226315211……32111300……121300㈤一般處理過(guò)程是：①在i+1,i+2,…,n項(xiàng)中，找出比b[I,1]大的最長(zhǎng)長(zhǎng)度L以及位置K;②假設(shè)L>0，那么b[I,2]:=L+1;b[I,3]:=k;最后此題經(jīng)過(guò)計(jì)算，其數(shù)據(jù)存儲(chǔ)表如下：123456789101112131413791638243718441921226315787634352432114348979101311121300初始化:for(i=1;i<=n;i++){cin>>b[i][1];b[i][2]=1;b[i][3]=0;}下面給出求最長(zhǎng)不下降序列的算法:for(i=n-1;i>=1;i--){l=0;k=0;for(j=i+1;j<=n;j++)if((b[j][1]>b[i][1])&&(b[j][2]>l)){l=b[j][2];k=j;}if(l>0){b[i][2]=l+1;b[i][3]=k;}}下面找出最長(zhǎng)不下降序列：k=1;for(j=1;j<=n;j++)if(b[j][2]>b[k][2])k=j;最長(zhǎng)不下降序列長(zhǎng)度為b[k][2]序列while(k!=0){cout<<’’<<b[k][1];k=b[k][3];}#include<iostream>usingnamespacestd;intmain(){intn,i,j,l,k,b[200][10];cout<<"inputn:"<<endl;cin>>n;for(i=1;i<=n;i++)//輸入序列的初始值

{cin>>b[i][1];b[i][2]=1;b[i][3]=0;}

程序運(yùn)行結(jié)果：輸入：1413791638243718441921226315輸出：max=879161819212263

for(i=n-1;i>=1;i--)//求最長(zhǎng)不下降序列

{l=0;k=0;for(j=i+1;j<=n;j++)if((b[j][1]>b[i][1])&&(b[j][2]>l)){l=b[j][2];k=j;}if(l>0){b[i][2]=l+1;b[i][3]=k;}}k=1;for(j=1;j<=n;j++)//求最長(zhǎng)不下降序列的起始位置

if(b[j][2]>b[k][2])k=j;cout<<"max="<<b[k][2]<<endl;//輸出結(jié)果

while(k!=0)//輸出最長(zhǎng)不下降序列

{cout<<''<<b[k][1];k=b[k][3];}}攔截導(dǎo)彈(Noip1999)某國(guó)為了防御敵國(guó)的導(dǎo)彈襲擊，開(kāi)展出一種導(dǎo)彈攔截系統(tǒng)。但是這種導(dǎo)彈攔截系統(tǒng)有一個(gè)缺陷：雖然它的第一發(fā)炮彈能夠到達(dá)任意的高度，但是以后每一發(fā)炮彈都不能高于前一發(fā)的高度。某天，雷達(dá)捕捉到敵國(guó)的導(dǎo)彈來(lái)襲。由于該系統(tǒng)還在試用階段，所以只有一套系統(tǒng)，因此有可能不能攔截所有的導(dǎo)彈。輸入導(dǎo)彈依次飛來(lái)的高度〔雷達(dá)給出的高度數(shù)據(jù)是不大于30000的正整數(shù)，導(dǎo)彈數(shù)不超過(guò)1000〕，計(jì)算這套系統(tǒng)最多能攔截多少導(dǎo)彈，如果要攔截所有導(dǎo)彈最少要配備多少套這種導(dǎo)彈攔截系統(tǒng)。樣例：INPUTOUTPUT389207155300299170158656〔最多能攔截的導(dǎo)彈數(shù)〕2〔要攔截所有導(dǎo)彈最少要配備的系統(tǒng)數(shù)〕5.3線性動(dòng)歸【算法分析】第一問(wèn)即經(jīng)典的最長(zhǎng)不下降子序列問(wèn)題，可以用一般的DP算法，也可以用高效算法，但這個(gè)題的數(shù)據(jù)規(guī)模不需要。用a[x]表示原序列中第x個(gè)元素，b[x]表示長(zhǎng)度為x的不下降子序列的長(zhǎng)度，。當(dāng)處理第a[x]時(shí)，可查找它可以連接到長(zhǎng)度最大為多少的不下降子序列后〔即與局部b[x]比較〕。假設(shè)可以連到長(zhǎng)度最大為max的不下降子序列后，那么b[x]:=max+1。b數(shù)組被賦值的最大值就是第一問(wèn)的答案。5.3線性動(dòng)歸第二問(wèn)很容易想到貪心法：那就是采取屢次求最長(zhǎng)不上升序列的方法，然后得出總次數(shù)。上述貪心法不正確，很容易就能舉出反例。 例如：“7541632” 用屢次求最長(zhǎng)不上升序列所有為 “75432”、“1”、“6”共3套系統(tǒng)； 但其實(shí)只要2套，分別為： “7541”與“632”。那么，正確的做法又是什么呢？5.3線性動(dòng)歸上述問(wèn)題的原因是假設(shè)干次最優(yōu)決策值和不一定能推導(dǎo)出整個(gè)問(wèn)題的最優(yōu)。為了解決這個(gè)問(wèn)題下面介紹一個(gè)重要性質(zhì)：最少鏈劃分=最長(zhǎng)反鏈長(zhǎng)度為了證明這個(gè)性質(zhì)，需要了解離散數(shù)學(xué)中偏序集的相關(guān)概念和性質(zhì)以及偏序集的Dilworth定理。5.3線性動(dòng)歸偏序是在集合X上的二元關(guān)系≤〔這只是個(gè)抽象符號(hào)，不是“小于或等于”〕，它滿(mǎn)足自反性、反對(duì)稱(chēng)性和傳遞性。即，對(duì)于X中的任意元素a,b和c，有:自反性：a≤a;反對(duì)稱(chēng)性：如果a≤b且b≤a，那么有a=b;傳遞性：如果a≤b且b≤c，那么a≤c。帶有偏序關(guān)系的集合稱(chēng)為偏序集。令(X,≤)是一個(gè)偏序集，對(duì)于集合中的兩個(gè)元素a、b，如果有a≤b或者b≤a，那么稱(chēng)a和b是可比的，否那么a和b不可比。一個(gè)反鏈A是X的一個(gè)子集，它的任意兩個(gè)元素都不能進(jìn)行比較。一個(gè)鏈C是X的一個(gè)子集，它的任意兩個(gè)元素都可比。5.3線性動(dòng)歸在X中，對(duì)于元素a，如果任意元素b，都有a≤b，那么稱(chēng)a為極小元。定理1：令〔X,≤〕是一個(gè)有限偏序集，并令r是其最大鏈的大小。那么X可以被劃分成r個(gè)但不能再少的反鏈。其對(duì)偶定理稱(chēng)為Dilworth定理： 令〔X,≤〕是一個(gè)有限偏序集，并令m是反鏈的最大的大小。那么X可以被劃分成m個(gè)但不能再少的鏈。5.3線性動(dòng)歸要求最少的覆蓋，按照Dilworth定理最少鏈劃分=最長(zhǎng)反鏈長(zhǎng)度

所以最少多少套系統(tǒng)=最長(zhǎng)導(dǎo)彈高度上升序列長(zhǎng)度。知道了怎樣求最長(zhǎng)不上升算法，同樣也就知道了怎樣求最長(zhǎng)上升序列。時(shí)間復(fù)雜度O(n㏒n)。5.4坐標(biāo)型動(dòng)歸Robots在一個(gè)n*m的棋盤(pán)內(nèi)，一些格子里有垃圾要拾撿?，F(xiàn)在有一個(gè)能撿垃圾的機(jī)器人