c++編程入門第五次課

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

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

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

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

<=

T

<=

1000〕和M〔1

<=

M

<=

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

71100

691

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

<=

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

<=

100。5.2背包問題#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背包問題二、滿01背包有N件物品;第i件物品Wi公斤;第i件物品價值Ci元;現(xiàn)有一輛載重M公斤的卡車;問選取裝載哪些物品，使得卡車開車正好裝滿時，運送的總價值最大？ 假設(shè)無法裝滿卡車，那么輸出無解。5.2背包問題設(shè)F(i,j)表示前i件物品背包為j的最大效益，那么有1<=i<=N,0<=j<=N初值：F(0,j)=0，F(xiàn)(1,j)=-∞F(N,M)即答案顯然時間復(fù)雜度為O(NM)5.2背包問題三、帶條件的背包問題〔1〕有N件物品;第i件物品Wi公斤;第i件物品價值Ci元;第i件物品可能帶0~2個附件；假設(shè)裝載附件，必須裝載主件，反之沒有約束；現(xiàn)有一輛載重M公斤的卡車;問選取裝載哪些物品，使得卡車運送的總價值最大？5.2背包問題假設(shè)只有主件的情況，顯然與經(jīng)典背包問題完全相同！現(xiàn)在每個物品有附件，我們可以分成4種方案僅裝載主件裝載主件+第1個附件裝載主件+第2個附件裝載主件+2個附件由于上述4種并列，這是幾種不同的決策同時規(guī)劃即可5.2背包問題設(shè)F(i,j)表示前i件物品背包為j的最優(yōu)解，那么有，1<=i<=N,0<=j<=M時間復(fù)雜度O(NM)〔開心的金明〕5.2背包問題四、多層背包問題有N件物品;第i件物品Wi公斤;第i件物品價值Ci元;現(xiàn)有一輛載重M公斤的卡車;第i件物品限制最多只能取Xi個；問選取裝載哪些物品，使得卡車運送的總價值最大？5.2背包問題我們可以類似01背包問題，將第i種物品拆分成x[i]個，這樣每個物品只有1件了,如以下圖:然后對所有的物品采用動態(tài)規(guī)劃即可。F(i,j)=max{f(i-1,j-k*w[i])+k*c[i]}0<=k*w[i]<=j5.2背包問題五、完全背包問題有N件物品;第i件物品Wi公斤;第i件物品價值Ci元;現(xiàn)有一輛載重M公斤的卡車;每次可以選取某種物品的任意多件裝載；問選取裝載哪些物品，使得卡車運送的總價值最大？5.2背包問題類似多層背包問題將每個物品展開成X[i]=m/w[i]個，然后對所有的物品采用動態(tài)規(guī)劃即可。假設(shè)兩件物品i、j滿足c[i]<=c[j]且w[i]>=w[j],那么將物品i去掉,不用考慮。這個優(yōu)化的正確性顯然：任何情況下都可將價值小費用高的j換成物美價廉的i,得到至少不會更差的方案。由于每種物品有選和不選兩種情況，可以將每種物品的2k個當(dāng)成一個整體考慮。這樣對于某種物品要選取多個，都可以由假設(shè)干個2k個物品進行組合(即2進制數(shù))。例如第i種物品要選10個，那么10=23+21。這樣第i種物品的個數(shù)為k=㏒2(m/wi)物品，是一個很大的改進。進一步,在計算k時,K=㏒2(j/wi),j為當(dāng)前背包剩余空間。5.2背包問題fori:=1tondo//動態(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;在這里為了使得每個物品只取1個或不取,采用了每次取j都是與i-1進行比較，實際上保存了每1步取不同j的值5.2背包問題事實上，我們只關(guān)心剩余背包的最大值，也就是僅僅關(guān)心f(j),因此，在對f(j)更新時，只要背包容量可以，那么可以反復(fù)更新。程序如下： fori:=1tondo//動態(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背包問題對于背包問題，我們可以看出，問題描述必須有一個根本要素：資源，有時這種資源可能是金錢、空間或者時間，問題就是要對這些資源如何分配，一種根本的想法是將資源應(yīng)用于前i個階段，然后考慮第i個階段和前i-1個階段之間的關(guān)系。設(shè)前i個點的消耗j的資源得到的最優(yōu)值，研究前i-1個點消耗的資源的最優(yōu)值，利用第i個點決策轉(zhuǎn)移，如以下圖。狀態(tài)轉(zhuǎn)移方程一般可寫成:fi(j)=min{fi-1(k)+ui(j,k)}5.3線性動歸線性動歸即為常規(guī)的動歸題目，狀態(tài)轉(zhuǎn)移為線性求最長不下降序列㈠問題描述：設(shè)有由n個不相同的整數(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)那么稱為長度為e的不下降序列。程序要求，當(dāng)原數(shù)列出之后，求出最長的不下降序列。例如13，7，9，16，38，24，37，18，44，19，21，22，63，15。例中13，16，18，19，21，22，63就是一個長度為7的不下降序列，同時也有7，9，16，18，19，21，22，63長度為8的不下降序列。㈡算法分析：根據(jù)動態(tài)規(guī)劃的原理，由后往前進行搜索(當(dāng)然從前往后也一樣)。1·對b(n)來說，由于它是最后一個數(shù)，所以當(dāng)從b(n)開始查找時，只存在長度為1的不下降序列；2·假設(shè)從b(n-1)開始查找，那么存在下面的兩種可能性：①假設(shè)b(n-1)<b(n)那么存在長度為2的不下降序列b(n-1)，b(n)。②假設(shè)b(n-1)>b(n)那么存在長度為1的不下降序列b(n-1)或b(n)。3·一般假設(shè)從b(i)開始，此時最長不下降序列應(yīng)該按以下方法求出:在b(i+1),b(i+2),…,b(n)中，找出一個比b(i)大的且最長的不下降序列，作為它的后繼。㈢數(shù)據(jù)結(jié)構(gòu)：為算法上的需要，定義一個整數(shù)類型二維數(shù)組b(N,3)1·b(I,1)表示第I個數(shù)的數(shù)值本身；2·b(I,2)表示從I位置到達N的最長不下降序列長度

3·b(I,3)表示從I位置開始最長不下降序列的下一個位置，假設(shè)b[I,3]=0那么表示后面沒有連接項。㈣求解過程：①從倒數(shù)第二項開始計算，后面僅有1項，比較一次，因63>15，不符合要求，長度仍為1。②從倒數(shù)第三項開始其后有2項，需做兩次比較，得到目前最長的不下降序列為2，如下表：11121314……11121314226315……21226315211……32111300……121300㈤一般處理過程是：①在i+1,i+2,…,n項中，找出比b[I,1]大的最長長度L以及位置K;②假設(shè)L>0，那么b[I,2]:=L+1;b[I,3]:=k;最后此題經(jīng)過計算，其數(shù)據(jù)存儲表如下：123456789101112131413791638243718441921226315787634352432114348979101311121300初始化:for(i=1;i<=n;i++){cin>>b[i][1];b[i][2]=1;b[i][3]=0;}下面給出求最長不下降序列的算法: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;}}下面找出最長不下降序列：k=1;for(j=1;j<=n;j++)if(b[j][2]>b[k][2])k=j;最長不下降序列長度為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;}

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

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;}}k=1;for(j=1;j<=n;j++)//求最長不下降序列的起始位置

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

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

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

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