第一篇：動(dòng)態(tài)規(guī)劃總結(jié)經(jīng)典題目(經(jīng)典中的經(jīng)典)
動(dòng)態(tài)規(guī)劃總結(jié)——經(jīng)典問題總結(jié)
本文著重討論狀態(tài)是如何表示，以及方程是怎樣表示的。當(dāng)然，還附上關(guān)鍵的，有可能作為模板的代碼段。但有的代碼的實(shí)現(xiàn)是優(yōu)化版的。
經(jīng)典問題總結(jié)
最長(zhǎng)上升子序列（LIS）
問題描述如下:
設(shè)L=
有了以上的思想，DP方程就呼之欲出了（這里是順序推的，不是逆序的）： DP[I]=MAX（1,DP[J]+1）J=0,1,...,I-1
但這樣的想法實(shí)現(xiàn)起來是）O(n^2)的。本題還有更好的解法，就是O(n*logn)。利用了長(zhǎng)升子序列的性質(zhì)來優(yōu)化，以下是優(yōu)化版的代碼：
//最長(zhǎng)不降子序 const int SIZE=500001;int data[SIZE];int dp[SIZE];
//返回值是最長(zhǎng)不降子序列的最大長(zhǎng)度,復(fù)雜度O(N*logN)
int LCS(int n){ //N是DATA數(shù)組的長(zhǎng)度,下標(biāo)從1開始 int len(1),low,high,mid,i;
dp[1]=data[1];for(i=1;i<=n;++i){ low=1;high=len;
while(low<=high){ //二分 mid=(low+high)/2;if(data[i]>dp[mid]){ low=mid+1;} else {
high=mid-1;} }
dp[low]=data[i];if(low>len){ ++len;} }
return len;}
最長(zhǎng)公共子序列（LCS）
給出兩個(gè)字符串a(chǎn), b，求它們的最長(zhǎng)、連續(xù)的公共字串。
這很容易就想到以DP[I][J]表示A串匹配到I，B串匹配到J時(shí)的最大長(zhǎng)度。則：
0 I==0 || J==0
DP[I][J]=DP[I-1][J-1]+ 1 A[I]==B[J] MAX（DP[I-1][J]，DP[I][J-1]）不是以上情況
但這樣實(shí)現(xiàn)起來的空間復(fù)雜度為O(n^2)，而上面的方程只與第I-1行有關(guān)，所以可以用兩個(gè)一維數(shù)組來代替。以下是代碼：
//最長(zhǎng)公共子序列
const int SIZE=1001;
int dp[2][SIZE];//兩個(gè)一維數(shù)組
//輸入兩個(gè)字符串，返回最大的長(zhǎng)度
int LCS(const string& a,const string& b){ int i,j,flag;
memset(dp,0,sizeof(dp));
flag=1;
for(i=1;i<=a.size();++i){ for(j=1;j<=b.size();++j){
if(a[i-1]==b[j-1])dp[flag][j]=dp[1-flag][j-1]+1;else dp[flag][j]=MAX(dp[flag][j-1],dp[1-flag][j]);}
flag=1-flag;}
return dp[1-flag][b.size()];}
01背包
有N件物品和一個(gè)容量為V的背包。第i件物品的大小是c[i]，價(jià)值是w[i]。求解將哪些物品裝入背包可使價(jià)值總和最大。
用DP[I][J] 表示前I件物品放入一個(gè)容量為J的背包可以獲得的最大價(jià)值。則 DP[I][J]= DP[I-1][J] ,J MAX（DP[I-1][J]，DP[I-1][J-C[I]]+W[I]）, J>=C[I] 這樣實(shí)現(xiàn)的空間復(fù)雜度為O(VN)，實(shí)際上可以優(yōu)化到O（V）。以下是代碼： const int MAXW=13000;//最大重量 const int MAXN=3450;//最大物品數(shù)量 int c[MAXN];//物品的存放要從下標(biāo)1開始 int w[MAXN];//物品的存放要從下標(biāo)1開始 int dp[MAXW]; //不需要將背包裝滿，則將DP數(shù)組全部初始化為0 //要將背包裝滿，則初始化為DP[0]=0，DP[1]…DP[V]=-1(即非法狀態(tài))int Packet(int n,int v){ int i,j; memset(dp,0,sizeof(dp));for(i=1;i<=n;++i){ for(j=v;j>=c[i];--j){ //這里是倒序，別弄錯(cuò)了 dp[j]=MAX(dp[j],dp[j-c[i]]+w[i]);} } return dp[v];} 完全背包問題 有N種物品和一個(gè)容量為V的背包，每種物品都有無限件可用。第i種物品的費(fèi)用是c[i]，價(jià)值是w[i]。求解將哪些物品裝入背包可使這些物品的費(fèi)用總和不超過背包容量，且價(jià)值總和最大。 很容易可以得到這種狀態(tài)表示：用DP[I][J] 表示前I件物品放入一個(gè)容量為J的背包可以獲得的最大價(jià)值。則 DP[I][J]=MAX（DP[I-1][J]，DP[I-1][J-K*C[I]]+K*W[I]）0<=K*C[I]<=J 這樣的復(fù)雜度是O(V*Σ(V/c[i])) 有更好的做法，那就是利用01背包的優(yōu)化原理。在優(yōu)化的代碼中，之所以第二重循環(huán)是倒序，是為了防止重復(fù)拿，那么只要將其變?yōu)轫樞蚣纯梢灾貜?fù)取。代碼就不給了。 多重背包問題 有N種物品和一個(gè)容量為V的背包。第i種物品最多有n[i]件可用，每件費(fèi)用是c[i]，價(jià)值是w[i]。求解將哪些物品裝入背包可使這些物品的費(fèi)用總和不超過背包容量，且價(jià)值總和最大。 這題仍然可以用到上一題的思想，DP表示狀態(tài)與上面的相同。方程為： DP[I][J]=MAX（DP[I-1][J]，DP[I-1][J-K*C[I]]+K*W[I]） 不同的是K的范圍，0<=K<=N[I] && 0<=K*C[I]<=J 這樣的復(fù)雜度為O(V*Σn[i])。有更好的想法就是先用二進(jìn)制來劃分。將第i種物品分成若干件物品，其中每件物品有一個(gè)系數(shù)，這件物品的費(fèi)用和價(jià)值均是原來的費(fèi)用和價(jià)值乘以這個(gè)系數(shù)。使這些系數(shù)分別為1,2,4,...,2^(k-1),n[i]-2^k+1，且k是滿足n[i]-2^k+1>0的最大整數(shù)。然后用01背包做，這樣的復(fù)雜度為O(V*Σlog n[i])。關(guān)鍵代碼： const int SIZE=1001;int dp[SIZE]; int num[SIZE],c[SIZE],w[SIZE];//num[i]是I物品的件數(shù),C[I]是費(fèi)用，W[I]是價(jià)值 int MultiPack(int n,int v){ //存入?yún)?shù)，N是物品種類數(shù)，V是背包容量 int i,j,k; memset(dp,0,sizeof(dp)); for(i=1;i<=n;++i){ //存放物品的數(shù)組下標(biāo)從1開始 if(c[i]*num[i]>=v){ for(j=c[i];j<=v;++j){ dp[j]=MAX(dp[j],dp[j-c[i]]+w[i]);} } else { //使用二進(jìn)制劃分 k=1; while(k dp[j]=MAX(dp[j],dp[j-k*c[i]]+k*w[i]);} num[i]-=k;k*=2;} for(j=v;j>=num[i]*c[i];--j){ dp[j]=MAX(dp[j],dp[j-num[i]*c[i]]+num[i]*w[i]);} } } return dp[v];} 狀態(tài)表示總結(jié) 一維的狀態(tài)表示 DP的表示形式通常為：DP[I]表示取到第I個(gè)/種物品時(shí)的最優(yōu)值。DP方程的形式：DP[I]=MAX（DP[I]，DP[J]+P[I]）其中0<=J 有一些題可能要將一些額外的東西也認(rèn)為是物品。如HDU2059龜兔賽跑這題，需要將開始點(diǎn)和終點(diǎn)也認(rèn)為是加油站，然后才以DP[I]表示到第I個(gè)加油站并加滿油的最短時(shí)間。 有一些題可以將看似二維的情況轉(zhuǎn)化為一維的情況來做。如HDU 1081這題。大意是給出一個(gè)含有正數(shù)和負(fù)數(shù)的N階矩陣，求一個(gè)子矩陣使得子矩陣內(nèi)所有數(shù)的和最大。這樣的題可以將幾行合并為一行做。即枚舉就將第I行到第J行合并為一行，然后再用DP[K]=MAX（DP[K-1]，0）+ARR[K]，K是表示第K列。 有一些題是DP與暴力相結(jié)合，如POJ 3267 The Cow Lexicon這題。大意是給出一個(gè)長(zhǎng)的字符串，還有若干個(gè)短的字符串，問長(zhǎng)字符中至少要?jiǎng)h除幾個(gè)字符才能使得長(zhǎng)字符串中的子字符串都與某個(gè)短字符串相對(duì)應(yīng)。dp[i]表示從I到LEN-1需要?jiǎng)h除的最少字符串?dāng)?shù)，則dp[i]=min(dp[i+1]+1，dp[k]+del)其中dp[i+1]+1是沒有找到匹配的情況，dp[k]+del是有匹配的情況,K表示從I開始匹配,到匹配完后的最后一個(gè)字符的位置,DEL表示在匹配過程中要?jiǎng)h除的字符數(shù)。由于方程的特點(diǎn)，要從最后一個(gè)字符向第一個(gè)字符推去。中間要?jiǎng)h除的字符數(shù)用暴力找出。 有一些題用DP來枚舉全部的范圍，如POJ 1925 Spiderman這題。用DP[I]表示到達(dá)這個(gè)位置的最小跳數(shù)。其中DP數(shù)組為dp[1000005]，這是可能跳到的全部范圍。 二維狀態(tài)表示 通常是用來處理兩種事物。DP[I][J]通常表示A的前I個(gè)和B的前J個(gè)XX的最優(yōu)值。 DP方程之一：DP[I][J]=MAX（DP[I-1][J-1]+P[XX]，DP[I][J-1]+P[YY]，DP[I-1][J]+P[ZZ]）這里的XX，YY，ZZ是表示某某狀態(tài)得到的結(jié)果。 DP方程之二：DP[I][J]=MAX（DP[I][J]，DP[I-1][K]+P[I][J]），其中0<=K 對(duì)第三種DP方程舉個(gè)例：POJ 3280 Cheapest Palindrome這題。大意是給出一個(gè)字符串，你可在任意位置增加或刪除字符，每增加或刪除一個(gè)字符都有一個(gè)對(duì)應(yīng)的代價(jià)，求將其變?yōu)榛匚拇淖钚〈鷥r(jià)。以dp[i][j]表示從i到j(luò)要變成回文字符串的最小代價(jià)，則 dp[i][j] = min{ dp[i+1][j] + {去掉X的代價(jià)}，dp[i+1][j] + {加上X的代價(jià)}，dp[i][j-1]+ {去掉Y的代價(jià)}，dp[i][j-1] +{加上Y的代價(jià)}}； 算DP[I][J]時(shí)，要知道DP[I+1][J]的值，對(duì)于這類DP其實(shí)現(xiàn)方法如下所示： for(t=1;t 有時(shí)可以將DP與HASH相結(jié)合。如：POJ 1054 The Troublesome Frog這題。大意是在一個(gè)坐標(biāo)系中給出N個(gè)點(diǎn)，求找出以哪兩點(diǎn)作一條直線經(jīng)過的點(diǎn)數(shù)最多。以DP[I][J]表示過第J點(diǎn)和第I點(diǎn)的直線一共經(jīng)過的點(diǎn)數(shù)。DP[I][J]=（DP[J][INDEX]+1，-INF），先算出INDEX這點(diǎn)的坐標(biāo)，然后用哈希查找，如果找到，則執(zhí)行DP[J][INDEX]+1，如果找不到則用-INF表示不存在。 對(duì)于整除類型的題，如果要用DP做，那么其中有一維通常是佘數(shù)。如：POJ 1745Divisibility這題，dp[i][j]表示對(duì)前I個(gè)數(shù)進(jìn)行了處理,余數(shù)為J的情況 帶偏移的狀態(tài)表示 DP的表示形式通常為：DP[I][J]表示到第I個(gè)XX時(shí)，YY與ZZ之差為J時(shí)的最優(yōu)值。例如：POJ 1837這題。 題目大意：給出天平c個(gè)掛鉤的位置,然后給出g個(gè)物品的質(zhì)量,將物品掛在天平上,問使天平平衡的方法有幾種。 思想：用l[i]表示第i個(gè)點(diǎn)的x坐標(biāo)值，用w[i]表示第i個(gè)砝碼的重量，用dp[i][j]表示加了i個(gè)砝碼，兩邊力矩之差為j的可能方法數(shù)，則本題只要計(jì)算出dp[i][0]，即最終力矩差為0的方法數(shù)即可。由于質(zhì)量差可能為負(fù)，這里加上一個(gè)偏移量，考慮原題的數(shù)據(jù)可知，要想平衡，則一邊力矩至多為15*25*10=3750，故每個(gè)j加上3750。狀態(tài)轉(zhuǎn)移方程：dp[i+1][k+w[i]*l[j]]+= dp[i][k]，i=0~g，j=0~c，k=0~7500。輸出結(jié)果：dp[w][3750] 動(dòng)態(tài)規(guī)劃變態(tài)總結(jié) by zeus 1：Pku acm 1163 the Triangle 2：Pku acm 1953 World Cup Noise //說白了就是斐波那切數(shù)列 3：Pku acm 1458 Common Subsequence Lcs 4：Pku acm 2250 Compromise記錄路徑的lcs 5：Pku acm 1159 Palindrome 回文串 6：Pku acm 1080 Humman Gene Function 7：Pku acm 2192 Zipper 判斷2個(gè)字符串能否組成1個(gè)字符串 8：Pku acm 3356 AGTC 一個(gè)字符串到另一個(gè)的最小步驟 9：Pku acm 1887 Testing the CATCHER最長(zhǎng)下降子序列 10：Pku acm 2533 Longest Ordered Subsequence最長(zhǎng)上升子序列 11：Pku acm 1631 Bridging signals最長(zhǎng)上升子序列的加強(qiáng)版….二分法 12：Pku acm 1157 LITTLE SHOP OF FLOWERS 13：Pku acm 1088 滑雪 14：Pku 1050 To the Max 15：Pku 1050 To the Max最大線段和的加強(qiáng)板…..二維的 16：Pku 1014 dividing 17: Pku acm 1160 post office 18: pku acm 1015 Jury Compromise 19: hdoj 2546飯卡 20:pku 1837 Balance 21: pku 3267 The Cow Lexicon 22:Pku 1742 Coins //走塔....經(jīng)典的dp #include “iostream” using namespace std;int max(int a,int b){ return a>b?a:b;} int main(){ int n,i,j; int a[100][100]; int f[100];while(scanf(“%d”,&n)>0){ for(i=0;i for(j=0;j<=i;j++) { scanf(“%d”,&a[i][j]); if(i==n-1) f[j]=a[i][j]; } for(i=n-2;i>=0;i--) { for(j=0;j<=n-1;j++) if(f[j]>f[j+1]) f[j]=f[j]+a[i][j]; else f[j]=f[j+1]+a[i][j]; } printf(“%dn”,f[0]);} system(“pause”);} 2：Pku acm 1953 World Cup Noise //說白了就是斐波那切數(shù)列 #include “iostream” using namespace std;int main(){ int n,m; int i; int f[100]; f[0]=2; f[1]=3; scanf(“%d”,&n); for(i=2;i<100;i++) { f[i]=f[i-1]+f[i-2]; } for(i=0;i { scanf(“%d”,&m); { printf(“Scenario #%d:n%dnn”,i+1,f[m-1]); } } } 3：Pku acm 1458 Common Subsequence Lcs經(jīng)典 #include “iostream” #include “cstring” using namespace std;int setmax(int a,int b){ if(a>b) return a; else return b;} int f[8100][8100];main(){ char s1[800]; char s2[800]; int i,j; int sl1,sl2; while(scanf(“%s %s”,&s1,&s2)!=EOF) { sl1=strlen(s1); sl2=strlen(s2); for(i=0;i { f[0][i]=0; f[i][0]=0; } for(i=1;i for(j=1;j { if(s1[i-1]==s2[j-1]) f[i][j]=f[i-1][j-1]+1; else f[i][j]=setmax(f[i-1][j],f[i][j-1]); } printf(“%dn”,f[i-1][j-1]); } } 4：Pku acm 2250 Compromise記錄路徑的lcs #include “iostream” #include “string” using namespace std;#define N 100 struct node { string s;}s1[N],s2[N];int f[N][N];int path[N][N];string temp;int flag;void lcs(int i,int j){ if(i==0||j==0)return; if(path[i][j]==1){ lcs(i-1,j-1); { if(flag!=1){ cout< flag=1;} else cout< } else if(path[i][j]==2)lcs(i-1,j); else lcs(i,j-1);} int main(){ int i=0,j; int len1,len2; while(cin>>s1[0].s) { memset(f,0,sizeof(f)); i=1; while(1){ cin>>temp; if(temp==“#”)break; s1[i++].s=temp; } len1=i; i=0; while(1){ cin>>temp; if(temp==“#”)break; s2[i++].s=temp; } len2=i; memset(path,0,sizeof(path)); for(i=0;i<=len1;i++) for(j=0;j<=len2;j++) if(i==j)f[i][j]=1; for(i=1;i<=len1;i++) for(j=1;j<=len2;j++) { if(s1[i-1].s==s2[j-1].s) { f[i][j]=f[i-1][j-1]+1; path[i][j]=1; } else if(f[i-1][j]>=f[i][j-1]) { f[i][j]=f[i-1][j]; path[i][j]=2; } else { f[i][j]=f[i][j-1]; path[i][j]=3; } } flag=1; lcs(len1,len2); cout< } } 5：Pku acm 1159 Palindrome 回文串 帶有些許優(yōu)化的lcs #include “iostream” #include “string” #include “algorithm” using namespace std;int a[5005],b[5005];int c[3],d[3];string s1,s2;int main(){ int m,n=0; int i,j; while(cin>>n) { if(n==0)break; cin>>s1; } } s2=s1;reverse(s2.begin(),s2.end()); memset(a,0,sizeof(a)); memset(b,0,sizeof(b));for(i=0;i { b[0]=0; for(j=0;j { if(s1[i]==s2[j]) { b[j+1]=a[j]+1; } else if(b[j]>a[j+1]) { b[j+1]=b[j]; } else if(b[j] { b[j+1]=a[j+1]; } } for(j=0;j<=n;j++) a[j]=b[j]; } printf(“%dn”,n-b[n]);14 6：Pku acm 1080 Humman Gene Function #include “iostream” using namespace std;int f[250][250];int g[250][250];char s1[180];char s2[180];int maxnum(int x,int y,int z){ int zz= x>y?x:y; return zz>z?zz:z;} void make(){ f[1][1]=5;f[1][2]=-1;f[1][3]=-2;f[1][4]=-1;f[1][5]=-3; f[2][1]=-1;f[2][2]=5;f[2][3]=-3;f[2][4]=-2;f[2][5]=-4; f[3][1]=-2;f[3][2]=-3;f[3][3]=5;f[3][4]=-2;f[3][5]=-2; f[4][1]=-1;f[4][2]=-2;f[4][3]=-2;f[4][4]=5;f[4][5]=-1; f[5][1]=-3;f[5][2]=-4;f[5][3]=-2;f[5][4]=-1;f[5][5]=-99999;} int sw(char ch){ if(ch=='A') return 1; else if(ch=='C') return 2; else if(ch=='G') return 3; else if(ch=='T') return 4; else if(ch=='-') return 5;} int find(char ch1,char ch2){ return f[sw(ch1)][sw(ch2)];} int main(){ make(); int sl1,sl2,i,j,m; memset(g,0,sizeof(0)); cin>>m; while(m--) { cin>>sl1; cin>>s1; cin>>sl2; cin>>s2; for(i=1;i<=sl2;i++) g[0][i] = g[0][i-1]+find('-',s2[i-1]); for(i=1;i<=sl1;i++) g[i][0] = g[i-1][0]+find(s1[i-1],'-'); for(i=1;i<=sl1;i++) for(j=1;j<=sl2;j++) { g[i][j]=maxnum(g[i][j-1]+find('-',s2[j-1]),g[i-1][j]+find(s1[i-1],'-'),g[i-1][j-1]+find(s1[i-1],s2[j-1])); } cout< 7：Pku acm 2192 Zipper 判斷2個(gè)字符串能否組成1個(gè)字符串 //用動(dòng)態(tài)規(guī)劃解決，ok[i][j]表示str1長(zhǎng)度為i的前綴和str2長(zhǎng)度為j的后綴能否組成目標(biāo)中str中長(zhǎng)度為i+j的前綴串 #include “iostream” using namespace std;int i,j,n;int sl1,sl2,sl3;char s1[500],s2[500],s3[500];int f[500][500];int main(){ int count=0; scanf(“%d”,&n); while(n--) {count++; memset(f,0,sizeof(f)); scanf(“%s %s %s”,s1,s2,s3); sl1=strlen(s1); sl2=strlen(s2); sl3=strlen(s3); for(j=0;j { if(s1[j]==s3[j]) f[j+1][0]=1; else break; } for(i=0;i { if(s2[i]==s3[i]) f[0][i+1]=1; else break; } for(i=0;i<=sl1;i++) for(j=0;j<=sl2;j++) { if(!(i==0&&j==0)) if(s1[i]==s3[i+j]&&f[i][j]==1) f[i+1][j]=1; if(s2[j]==s3[i+j]&&f[i][j]==1) f[i][j+1]=1; } printf(“Data set %d: ”,count); if(f[sl1][sl2]==1) printf(“yesn”); else printf(“non”); } } 8：Pku acm 3356 AGTC 一個(gè)字符串到另一個(gè)的最小步驟 #include “iostream” #include “string” using namespace std;int setmin(int x,int y,int z){ int xx=x>y?y:x; return xx>z?z:xx;} string s1,s2;int f[1005][1005];int main(){ int n,m; int i,j; while(cin>>n) { cin>>s1; cin>>m; cin>>s2; for(i=0;i<=n;i++) f[i][0]=i; for(i=0;i<=m;i++) f[0][i]=i; for(i=1;i<=n;i++) for(j=1;j<=m;j++) { if(s1[i-1]==s2[j-1]) f[i][j]=setmin(f[i-1][j]+1,f[i][j-1]+1,f[i-1][j-1]); else f[i][j]=setmin(f[i-1][j]+1,f[i][j-1]+1,f[i-1][j-1]+1); } cout< } } 9：Pku acm 1887 Testing the CATCHER最長(zhǎng)下降子序列 #include “iostream” using namespace std;int a[32769],f[32769];int main(){ int i,j,n,max; int count=0; while(1) { count++; scanf(“%d”,&a[0]); if(a[0]==-1)break; i=1; while(1) { scanf(“%d”,&a[i]); if(a[i]==-1) break; i++; } n=i; max=0; memset(f,0,sizeof(f)); for(i=1;i<=n;i++) { f[i]=1; for(j=0;j<=i;j++) { if(a[j-1]>a[i-1]&&f[j]+1>f[i]) f[i]=f[j]+1; if(f[i]>max) max=f[i]; } } printf(“Test #%d:n”,count); printf(“ maximum possible interceptions: %dnn”,max); } } 10：Pku acm 2533 Longest Ordered Subsequence最長(zhǎng)上升子序列 #include “iostream” using namespace std;int f[10000];int a[10000];int main(){ int n,i,j,max; while(scanf(“%d”,&n)!=EOF) { for(i=0;i { scanf(“%d”,&a[i]); } memset(f,0,sizeof(f)); max=0; for(i=1;i<=n;i++) { f[i]=1; for(j=0;j<=i;j++) if(a[j-1] f[i]=f[j]+1; if(f[i]>max) max=f[i]; } printf(“%dn”,max); } } 11：Pku acm 1631 Bridging signals最長(zhǎng)上升子序列的加強(qiáng)版….二分法 #include “iostream” #include “string” using namespace std;#define N 50000 int f[N];int a[N];int main(){ int n,m,i,j,max; scanf(“%d”,&n); while(n--) { max=-99; memset(f,0,sizeof(f)); scanf(“%d”,&m); for(i=0;i { scanf(“%d”,&a[i]); // f[i]=a[i]; } f[1]=a[0]; int s=1; int l,r,mid; for(i=1;i { if(f[s] f[++s]=a[i]; else { l=0; r=s; mid=(l+r)>>1; while(l<=r) { mid=(l+r)>>1; f[mid] } f[l]=a[i]; } } printf(“%dn”,s);} } 12：Pku acm 1157 LITTLE SHOP OF FLOWERS 該題也是經(jīng)典的動(dòng)態(tài)規(guī)劃，題目敘述的依然很麻煩，其實(shí)簡(jiǎn)化一下就是這樣的：例如下面這個(gè)例子就是：3表示行，5表示列，然后在下面的3行5列每一行選一個(gè)數(shù)，使這3個(gè)數(shù)最大，要求選的數(shù)列數(shù)必須依次增大，就是從左上方想右下方選3個(gè)數(shù)使和最大。3 5 7 23-5-24 16 5 21-4 10 23-21 5-4-20 20 #include “iostream” using namespace std;#define N 5000 int f[N][N];int w[N][N];int main(){ int n,m,i,j,k;while(cin>>n>>m){ for(i=0;i for(j=0;j cin>>w[i][j]; for(i=0;i for(j=0;j f[i][j]=-50000; for(i=1;i f[1][i]=w[0][i-1]; for(i=2;i<=n;i++) { for(j=1;j<=m;j++) { if(j>=i) for(k=1;k if(f[i][j] f[i][j]=f[i-1][k]+w[i-1][j-1]; } } int max=-50000; for(i=0;i<=m;i++) if(f[n][i]>max) max=f[n][i]; printf(“%dn”,max);} } 13：Pku acm 1088 滑雪 1 2 3 4 5 16 17 18 19 6 15 24 25 20 7 14 23 22 21 8 13 12 11 10 9 一個(gè)人可以從某個(gè)點(diǎn)滑向上下左右相鄰四個(gè)點(diǎn)之一，當(dāng)且僅當(dāng)高度減小。在上面的例子中，一條可滑行的滑坡為24-17-16-1。當(dāng)然25-24-23-...-3-2-1更長(zhǎng)。事實(shí)上，這是最長(zhǎng)的一條。輸出最長(zhǎng)區(qū)域的長(zhǎng)度。 #include “iostream” using namespace std;int h[100][100];int f[100][100];int dir[4][2]={{-1,0},{0,1},{1,0},{0,-1}};int r,c;bool judge(int x,int y){ if(x>=0&&y>=0&&x return true; else return false;} int dp(int i,int j){ int max=0,xi,yi,k; if(f[i][j]!=0) return f[i][j]; for(k=0;k<4;k++) { xi=i+dir[k][0]; yi=j+dir[k][1]; if(judge(xi,yi)&&h[i][j]>h[xi][yi]) { int num=dp(xi,yi); if(num>max) max=num; } } f[i][j]=max+1; return max+1;} int main(){ int i,j; int temp,max; while(cin>>r>>c) { for(i=0;i for(j=0;j { cin>>h[i][j]; } memset(f,0,sizeof(f)); max=0; for(i=0;i { for(j=0;j { temp=dp(i,j); max=max>temp?max:temp; } } cout< } } 14：hdoj1003 max num #include “iostream” using namespace std;int f[100005];int a[100005];int main(){ int num,n,i,j; int st,end,now,max; int flag; int count=0; int k;cin>>num; while(num--) { count++; cin>>n; for(i=0;i cin>>a[i]; now=0; max=-999; k=1; for(i=0;i { now+=a[i]; if(now>max) { max=now; end=i+1; st=k; } if(now<0) { now=0; k=i+2; } } printf(“Case %d:n”,count); printf(“%d %d %dn”,max,st,end); if(num!=0)printf(“n”); } return 0; } 15：Pku 1050 To the Max最大線段和的加強(qiáng)板…..二維的 #include “iostream” using namespace std;int n,i,j,cnt,now,maxx,k;int a[150][150];int s[150][150][150];int main(){ while(scanf(“%d”,&n)!=EOF) { for(i=1;i<=n;i++) for(j=1;j<=n;j++) { scanf(“%d”,&a[i][j]); s[i][i][j]=a[i][j]; } for(i=1;i for(j=i+1;j<=n;j++) for(k=1;k<=n;k++) { s[i][j][k]=s[i][j-1][k]+a[j][k]; } maxx=0; for(i=1;i<=n;i++) for(j=1;j<=n;j++) { cnt=0; now=0; for(k=1;k<=n;k++) { cnt+=s[i][j][k]; if(cnt>now) now=cnt; if(cnt<0) cnt=0; } if(now>maxx)maxx=now; } printf(“%dn”,maxx); } return 0;} 16：Pku 1014 dividing 實(shí)在不會(huì)做先抄個(gè)代碼 #include bool opt[60000]; int num=0; int mid,max; int stone[7]; int input() { scanf(“%d%d%d%d%d%d”,&stone[1],&stone[2],&stone[3],&stone[4],&stone[5],&stone[6]); if(!stone[6]&&!stone[1]&&!stone[2]&&!stone[3]&&!stone[4]&&!stone[5]){return 1;} //讀到末行 num++; printf(“Collection #%d:n”,num); mid=0; for(int i=1;i<=6;i++)mid+=stone[i]*i; if(mid % 2 ==1)//明顯的剪枝 { printf(“Can't be divided.nn”); return 2; } else mid/=2;//我們的任務(wù)就是求opt return 0; } void dp() { memset(opt,0,60000);//初始化，opt所有成員為false opt[0]=true;//opt[0]顯然是true max=0;//當(dāng)前最大值是0 for(int i=1;i<=6;i++) { if(stone[i]>0) { for(int j=max;j>=0;j--) // 從當(dāng)前最大值開始往下算 if(opt[j])//找到可行的j { if(opt[mid]) //判斷是否已經(jīng)求出結(jié)果 { printf(“Can be divided.nn”); return; } for(int k=1;k<=stone[i];k++)//在剛找到的可行j基礎(chǔ)上加石頭.{ if(j+k*i>mid || opt[j+k*i])break;//如果已經(jīng)大于總價(jià)值的一半mid，或opt[j+k*i]已計(jì)算，跳出循環(huán) opt[j+k*i]=true; } } } max=max+i*stone[i];//更新當(dāng)前最大值 if(max>mid)max=mid; //如果當(dāng)前最大值超過了mid，對(duì)其賦值為mid } printf(“Can't be divided.nn”);//如果從1到6循環(huán)完一遍后仍然沒有算出opt[mid]，說明無解 } int main() { while(1) { int t=input(); switch(t) { case 1 : return 0; //讀到末行，結(jié)束 case 2 : continue;//讀到明顯的剪枝 default : dp(); } } return 0; } 17: Pku acm 1160 post office 貼代碼 題目給出m個(gè)村莊及其距離，給出n個(gè)郵局，要求怎么建n個(gè)郵局使代價(jià)最小。思路：用opt[i][j]記錄把前i個(gè)郵局建到前j個(gè)村莊中的最優(yōu)解，用cost[i][j]記錄所有在i到j(luò)村莊中，建1個(gè)郵局的最小代價(jià)。顯然郵局應(yīng)該設(shè)到中點(diǎn)。讓前i個(gè)郵局覆蓋前j個(gè)村莊，第i+1個(gè)郵局覆蓋第j+1至j+k個(gè)村莊(j+k<=n)，則狀態(tài)轉(zhuǎn)移方程為 w[i+1][j+k]=min{w[i][j]+cost[j+1][j+k];}(k+j<=n)Cost數(shù)組存放從i到j(luò)中有一個(gè)郵局的最小代價(jià)，顯然該郵局應(yīng)該放在中間 W[i][j] 表示前i個(gè)郵局覆蓋前j個(gè)村莊的最小代價(jià)，對(duì)于i=1來說，w[i][j] = cost[i][j],讓前2個(gè)郵局覆蓋前j個(gè)村莊，也就是i=2的情況，可能是一下情況的最優(yōu)解：第一個(gè)郵局覆蓋第一個(gè)村莊，第二個(gè)村莊覆蓋2-j個(gè)村莊，或者第一個(gè)郵局覆蓋第1-2個(gè)村莊，第二個(gè)村莊覆蓋3-j個(gè)村莊，第一個(gè)郵局覆蓋第1-3個(gè)村莊，第二個(gè)村莊覆蓋4-j個(gè)村莊，等等等等 #include “iostream” using namespace std;int cost[310][310];int w[310][310];#define max 3000000 int main(){ int i,j,k,m,n,mid,q,v[310];while(scanf(“%d%d”,&m,&n)!=EOF){ for(i=1;i<=m;i++) scanf(“%d”,&v[i]); memset(cost,0,sizeof(cost)); for(i=1;i<=m;i++) for(j=i;j<=m;j++) { mid=(i+j)/2; for(k=i;k<=mid;k++) cost[i][j]=cost[i][j]+v[mid]-v[k]; for(k=mid+1;k<=j;k++) cost[i][j]=cost[i][j]+v[k]-v[mid]; } for(i=0;i<=n;i++) for(j=0;j<=m;j++) w[i][j]=max; w[0][0]=0; for(i=0;i<=n;i++) for(j=0;j<=m;j++) if(w[i][j] { for(k=1;k<=m-j;k++) { q=w[i][j]+cost[j+1][j+k]; if(w[i+1][j+k]>q) w[i+1][j+k]=q; } } printf(“%dn”, w[n][m]);} return 0;} 18: pku acm 1015 Jury Compromise 題目大意：在遙遠(yuǎn)的國(guó)家佛羅布尼亞，嫌犯是否有罪，須由陪審團(tuán)決定。陪審團(tuán)是由法官?gòu)墓娭刑暨x的。先隨機(jī)挑選n個(gè)人作為陪審團(tuán)的候選人，然后再?gòu)倪@n個(gè)人中選m人組成陪審團(tuán)。選m人的辦法是：控方和辯方會(huì)根據(jù)對(duì)候選人的喜歡程度，給所有候選人打分，分值從0到20。為了公平起見，法官選出陪審團(tuán)的原則是：選出的m個(gè)人，必須滿足辯方總分和控方總分的差的絕對(duì)值最小。如果有多種選擇方案的辯方總分和控方總分的之差的絕對(duì)值相同，那么選辯控雙方總分之和最大的方案即可。 分析：顯然本題如不用DP的話，顯然會(huì)超時(shí)。我們將第i個(gè)人的辯方和控方的差記錄在sub[i]中，將第i個(gè)人的辯方和控方的和記錄在plus[i]中，現(xiàn)在用f(j,k)表示取j個(gè)侯選人中，辯控和最大的那個(gè)方案。如果沒法選j個(gè)人使其控辯差為k的話，令f(j,k)=-1;本題的要求選出m個(gè)人，即最終解為f(m,k)，(-21*m<=k<=21*m)其中k的絕對(duì)值最小且有解。顯然f(j,k)是某個(gè)可行方案f(j-1,x)(-21*m<=x<=21*m)演變而來。可行方案f(j-1,x)演變成f(j,k)的條件是:存在某個(gè)侯選人i，它在方案f(j-1,x)中沒有被選上，且x+sub[i]=k,并且在所有滿足上述條件的方案中，f(j-1,x)+plus[i]最大。此時(shí)f(j-1,x)+plus[i]=f(j,k)。在上述推導(dǎo)中，另一個(gè)難點(diǎn)是如何標(biāo)記i是不是已經(jīng)在方案f(j-1,x)中。此時(shí)，我們可以用一個(gè)path(j,k)來記錄相應(yīng)的f(j,k)中最后選的人。例如上面的,則path(j,k)=i;倒數(shù)第二個(gè)人選的編號(hào)為path(j-1,k-sub[i]),依次類推，我們就能求出某個(gè)方案中所有人的編號(hào)。實(shí)際解題中，則于控辯差有可能為負(fù)，由于控辯差的范圍為[-21*m,21*m]我們可將所有控辯差加上m*21來解決，保證其值為正。#include int m,n;int f[21][850];int path[21][850];int PLUS[500],sub[500],ans[21],la,size;int main(){ int i,ii,jj,j,k,a,b,test=1; while(cin>>n>>m&&n+m) { size=21*m; for(i=1;i<=n;i++) { cin>>a>>b; PLUS[i]=a+b; sub[i]=a-b; } memset(f,-1,sizeof(f)); memset(path,-1,sizeof(path)); f[0][size]=0;path[0][size]=0; for(i=1;i<=n;i++)//先算出第1個(gè)人的編號(hào) { if(f[1][size+sub[i]] { path[1][size+sub[i]]=i; f[1][size+sub[i]]=PLUS[i]; } } for(i=1;i { for(j=0;j<2*size;j++) { if(path[i][j]>=0) { for(k=1;k<=n;k++) { if(f[i+1][j+sub[k]] { for(jj=i,ii=j;jj>=1;jj--)//順藤摸瓜.判斷第k個(gè)人有沒有出現(xiàn)過 { if(path[jj][ii]==k)break; ii-=sub[path[jj][ii]]; } if(jj<1) { path[i+1][j+sub[k]]=k; f[i+1][j+sub[k]]=f[i][j]+PLUS[k]; } } } } } } for(j=0;j<=2*size;j++)//取絕對(duì)值最小的作為最優(yōu)解 { if(f[m][size+j]>=0||f[m][size-j]>=0) { if(f[m][size+j]>f[m][size-j]) i=size+j; else i=size-j; break; } } cout<<“Jury #”< cout<<“Best jury has value ”<<(f[m][i]+i-size)/2<<“ for ”<<(f[m][i]-i+size)/2<<“ for defence:”< la=0; for(j=m,k=i;j>=1;j--) { ans[la++]=path[j][k]; k-=sub[ans[la-1]]; } sort(ans,ans+la);//排序輸出 for(i=0;i cout<<“ ”< cout< } return 0; prosecution and value } 19: hdoj 2546飯卡 電子科大本部食堂的飯卡有一種很詭異的設(shè)計(jì)，即在購(gòu)買之前判斷余額。如果購(gòu)買一個(gè)商品之前，卡上的剩余金額大于或等于5元，就一定可以購(gòu)買成功（即使購(gòu)買后卡上余額為負(fù)），否則無法購(gòu)買（即使金額足夠）。所以大家都希望盡量使卡上的余額最少。 某天，食堂中有n種菜出售，每種菜可購(gòu)買一次。已知每種菜的價(jià)格以及卡上的余額，問最少可使卡上的余額為多少。Input 多組數(shù)據(jù)。對(duì)于每組數(shù)據(jù)： 第一行為正整數(shù)n，表示菜的數(shù)量。n<=1000。 第二行包括n個(gè)正整數(shù)，表示每種菜的價(jià)格。價(jià)格不超過50。第三行包括一個(gè)正整數(shù)m，表示卡上的余額。m<=1000。n=0表示數(shù)據(jù)結(jié)束。 Output 對(duì)于每組輸入,輸出一行,包含一個(gè)整數(shù)，表示卡上可能的最小余額。Sample Input 1 50 5 10 1 2 3 2 1 1 2 3 2 1 50 0 Sample Output-45 32 #include #include using namespace std; int a[1002]; int b[1002]; void dfs(int x); int m; int sum,num,ans,flag; int main() { int i,j,k,n,t; while(scanf(“%d”,&n)!=EOF && n) { memset(b,0,sizeof(b)); sum = 0; for(i=0;i { scanf(“%d”,&a[i]); sum += a[i]; } scanf(“%d”,&m); if(sum+5 <= m)//如果余額很大的情況 { printf(“%dn”,m-sum); continue; } if(m < 5)//如果本來的余額小于5那么就不用計(jì)算了 { printf(“%dn”,m); continue; } sort(a,a+n); //開始遍歷: //找到臨界大于m-5的最小的和 ans = 0; num = m-5; for(i=n-2;i>=0;i--) { int maxnum = 0; for(j=i+1;j<=n-2;j++) { if((b[j] > maxnum)&&(a[i]+b[j]<=num)) maxnum = b[j]; } if(a[i]+maxnum == num) { ans = num; break; } else if(a[i]+maxnum < num) { b[i] = a[i]+maxnum; } if(b[i] > ans) ans = b[i]; } printf(“%dn”,m-ans-a[n-1]); } return 0; } 20:pku 1837 Balance 輸入一個(gè)天平若干（<=20）掛鉤的位置，將若干（<=20）砝碼掛到天平上，問有多少種使天平掛平衡的方法。 解題思路： 用一個(gè)二維數(shù)組a[x][y+mid]記錄掛x個(gè)砝碼時(shí)到y(tǒng)這個(gè)值的方法數(shù)，將砝碼一一掛上，最后記錄所有砝碼都掛上時(shí)的t[x][MID]的值，詳見代碼。狀態(tài)方程:a[i][j+value[i]*hook[k]]+=a[i-1][j];背包問題 #include “stdio.h” #include “stdlib.h” #define MID 7500 int a[21][2*MID];int val[21];int hook[21];int main(){ int m,n; int i,j,k; while(scanf(“%d%d”,&m,&n)!=EOF) { memset(a,0,sizeof(a)); for(i = 1;i<=m;i++) scanf(“%d”,&hook[i]); for(i = 1;i<=n;i++) scanf(“%d”,&val[i]); for(j = 1;j<=m;j++) a[1][val[1]*hook[j]+MID]++; for(i =2;i<=n;i++) for(j = 0;j<=2*MID;j++) for(k = 1;k<=m;k++) if(a[i-1][j]!=0) { a[i][j+val[i]*hook[k]]+=a[i-1][j]; } printf(“%dn”,a[n][MID]); } return 0;} 21: pku 3267 The Cow Lexicon 題目意思就是給出一個(gè)字符序列，同時(shí)給出已知的字符序列（單詞），問至少需要去掉多少個(gè)字符之后能夠?qū)⒔o出的字符序列變成已知的字符序列（單詞）的組合（根據(jù)題目意思，沒有字符是已知字符序列組合的一種情況）。 可以用s[i]表示從第一個(gè)字符到第i個(gè)字符中，滿足題目要求去掉的最少字符數(shù)。那么s[i]=min（num[k，i]+s[k-1]），其中num[k，i]表示從第k個(gè)字符到第i個(gè)字符匹配到某一個(gè)單詞時(shí)所需要的去掉的最少字符數(shù)。當(dāng)然匹配時(shí)是需要窮舉所有的單詞的。匹配的時(shí)候如果從前往后比較的話，需要加入剪枝（如果k+len[j]〉i的話肯定就是不行的），這樣的話就可以采取從后往前的比較方式，這樣之前需要將每個(gè)單詞的長(zhǎng)度保存到len[j]當(dāng)中。 #include scanf(“%s”,str+1); for(i=1;i<=m;i++){ scanf(“%s”,word[i]+1); len[i]=strlen(word[i]+1); } s[0]=0; for(i=1;i<=l;i++){ min=i; for(j=1;j<=m;j++){ pos_str=i; pos_word=len[j]; num=0; while(pos_str>=1&&pos_word>=1){ if(str[pos_str]==word[j][pos_word]){ pos_str--; pos_word--; } else { pos_str--; num++; } } if(pos_word<=0 && min>num+s[pos_str]){ min=num+s[pos_str]; } } s[i]=min; } printf(“%dn”,s[l]); } system(“PAUSE”); return 0;} 22:Pku 1742 Coins 編寫一個(gè)程序，讀入n，m。有幣值A(chǔ)1、A2、A3…、An的硬幣，對(duì)應(yīng)各有C1、C2、C3、…、Cn數(shù)量的硬幣，問它們能夠在1~m元中組合成多少中不同的幣值？ #include memset(dp,0,sizeof(dp));for(int i=1;i<=n;i++)scanf(“%d”,&a[i]);for(int i=1;i<=n;i++) scanf(“%d”,&c[i]);for(int i=0;i<2;i++)dp[i][0]=1;memset(flag,0,sizeof(flag));memset(flagans,0,sizeof(flagans));int from=0,to=1;for(int i=1;i<=n;i++){ memset(flag,0,sizeof(flag)); for(int j=1;j<=m;j++) { dp[to][j]=dp[from][j]; if(dp[to][j]==0&&j>=a[i]&&dp[to][j-a[i]]&&flag[j-a[i]]+1<=c[i]) { dp[to][j]=1; flagans[j]=1; flag[j]=flag[j-a[i]]+1; } } int temp; temp=from; from=to; to=temp;} int ans=0;for(int i=1;i<=m;i++){ // cout< ans+=flagans[i];} printf(“%dn”,ans);} system(“pause”);return 0;} 吉林師范大學(xué)計(jì)算機(jī)學(xué)院 教 案 課 程 名 稱 院系 級(jí) C 程序設(shè)計(jì)(算法部分) 計(jì)算機(jī)學(xué)院計(jì)算機(jī)科學(xué)與技術(shù)09級(jí) 教研室(系、實(shí)驗(yàn)室)計(jì)算機(jī)基礎(chǔ)教研室5101 授 課 班 級(jí) 09計(jì)算機(jī)科學(xué)與技術(shù)3班 實(shí)習(xí) 生 鄭言 系指導(dǎo)教師 滕國(guó)文 吉林師范大學(xué)計(jì)算機(jī)學(xué)院 二○一二年四月二十五日（星期三5，6節(jié)） 課型章節(jié)： 動(dòng)態(tài)規(guī)劃基本思想 基要本參教考材資和料主： 算法設(shè)計(jì)與分析》 教學(xué)目的： 本課程以C語(yǔ)言為教授程序設(shè)計(jì)的描述語(yǔ)言，結(jié)合語(yǔ)言介紹程序設(shè)計(jì)的基本原理、技巧和方法。主要講授內(nèi)容包括程序設(shè)計(jì)動(dòng)態(tài)規(guī)劃基本概念，動(dòng)態(tài)規(guī)劃的基本步驟，動(dòng)態(tài)規(guī)劃問題的特征。通過本課程的學(xué)習(xí)，為算法更好的學(xué)習(xí)，以及能用計(jì)算機(jī)解決一些實(shí)際問題打下堅(jiān)實(shí)的基礎(chǔ)。教學(xué)基本要求： 掌握C語(yǔ)言中動(dòng)態(tài)規(guī)劃的基本概念，動(dòng)態(tài)規(guī)劃的基本步驟，動(dòng)態(tài)規(guī)劃問題的特征。并能熟練使用C語(yǔ)言動(dòng)態(tài)規(guī)劃思想解決一些簡(jiǎn)單程序問題；掌握一些基本算法結(jié)構(gòu)及相關(guān)方法；熟悉程序設(shè)計(jì)的思想和編程技巧。重點(diǎn)： 動(dòng)態(tài)規(guī)劃基本概念，動(dòng)態(tài)規(guī)劃的基本步驟，動(dòng)態(tài)規(guī)劃問題的特征。難點(diǎn): 動(dòng)態(tài)規(guī)劃的基本步驟 課型： 理論課 教法： 1.多媒體講解 2.舉例講解 教學(xué)內(nèi)容及過程： 1.課前回顧： 枚舉法: 在進(jìn)行歸納推理時(shí)，如果逐個(gè)考察了某類事件的所有可能情況，因而得出一般結(jié)論，那么這結(jié)論是可靠的，這種歸納方法叫做枚舉法． 2.數(shù)塔問題 有形如下圖所示的數(shù)塔，從頂部出發(fā)，在每一結(jié)點(diǎn)可以選擇向左走或是向右走，一直走到底層，要求找出一條路徑，使路徑上的值最大。簡(jiǎn)單的進(jìn)行選舉方法的引導(dǎo)，讓同學(xué)們主動(dòng)思考到動(dòng)態(tài)規(guī)劃的思想上了。考慮一下： 從頂點(diǎn)出發(fā)時(shí)到底向左走還是向右走應(yīng)取決于是從左走能取到最大值還是從右走能取到最大值，只要左右兩道路徑上的最大值求出來了才能作出決策。 同樣，下一層的走向又要取決于再下一層上的最大值是否已經(jīng)求出才能決策。這樣一層一層推下去，直到倒數(shù)第二層時(shí)就非常明了。 如數(shù)字2，只要選擇它下面較大值的結(jié)點(diǎn)19前進(jìn)就可以了。所以實(shí)際求解時(shí)，可從底層開始，層層遞進(jìn)，最后得到最大值。 結(jié)論：自頂向下的分析，自底向上的計(jì)算。#include return x;else return y;} main(){ int a[100][100];int i,j,n;scanf(“%d”,&n);for(i=0;i for(j=0;j<=i;j++) scanf(“%d”,&a[i][j]);for(i=n-2;i>=0;i--) for(j=0;j<=i;j++) { a[i][j]+=max(a[i+1][j],a[i+1][j+1]); } printf(“%dn”,a[0][0]);} 3.總結(jié)“動(dòng)態(tài)規(guī)劃的基本思想” 如果各個(gè)子問題不是獨(dú)立的，不同的子問題的個(gè)數(shù)只是多項(xiàng)式量級(jí)，如果我們能夠保存已經(jīng)解決的子問題的答案，而在需要的時(shí)候再找出已求得的答案，這樣就可以避免大量的重復(fù)計(jì)算。由此而來的基本思路是，用一個(gè)表記錄所有已解決的子問題的答案，不管該問題以后是否被用到，只要它被計(jì)算過，就將其結(jié)果填入表中。 4.總結(jié)“動(dòng)態(tài)規(guī)劃的基本步驟” 動(dòng)態(tài)規(guī)劃算法通常用于求解具有某種最優(yōu)性質(zhì)的問題。在這類問題中，可能會(huì)有許多可行解。每一個(gè)解都對(duì)應(yīng)于一個(gè)值，我們希望找到具有最優(yōu)值（最大值或最小值）的那個(gè)解。設(shè)計(jì)一個(gè)動(dòng)態(tài)規(guī)劃算法，通常可以按以下幾個(gè)步驟進(jìn)行： （1）找出最優(yōu)解的性質(zhì)，并刻畫其結(jié)構(gòu)特征。（2）遞歸地定義最優(yōu)值。 （3）以自底向上的方式計(jì)算出最優(yōu)值。 （4）根據(jù)計(jì)算最優(yōu)值時(shí)得到的信息，構(gòu)造一個(gè)最優(yōu)解。 其中（1）——（3）步是動(dòng)態(tài)規(guī)劃算法的基本步驟。在只需要求出最優(yōu)值的情形，步驟（4）可以省去。若需要求出問題的一個(gè)最優(yōu)解，則必須執(zhí)行步驟（4）。此時(shí)，在步驟（3）中計(jì)算最優(yōu)值時(shí)，通常需記錄更多的信息，以便在步驟（4）中，根據(jù)所記錄的信息，快速構(gòu)造出一個(gè)最優(yōu)解。 5.總結(jié)“動(dòng)態(tài)規(guī)劃問題的特征” 動(dòng)態(tài)規(guī)劃算法的有效性依賴于問題本身所具有的兩個(gè)重要性質(zhì)： 1、最優(yōu)子結(jié)構(gòu)：當(dāng)問題的最優(yōu)解包含了其子問題的最優(yōu)解時(shí)，稱該問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)。 2、重疊子問題：在用遞歸算法自頂向下解問題時(shí)，每次產(chǎn)生的子問題并不總是新問題，有些子問題被反復(fù)計(jì)算多次。動(dòng)態(tài)規(guī)劃算法正是利用了這種子問題的重疊性質(zhì)，對(duì)每一個(gè)子問題只解一次，而后將其解保存在一個(gè)表格中，在以后盡可能多地利用這些子問題的解。6.思考： 《免費(fèi)餡餅》 題目描述: 都說天上不會(huì)掉餡餅，但有一天gameboy正走在回家的小徑上，忽然天上掉下大把大把的餡餅。說來gameboy的人品實(shí)在是太好了，這餡餅別處都不掉，就掉落在他身旁的10米范圍內(nèi)。餡餅如果掉在了地上當(dāng)然就不能吃了，所以gameboy馬上卸下身上的背包去接。但由于小徑兩側(cè)都不能站人，所以他只能在小徑上接。由于gameboy平時(shí)老呆在房間里玩游戲，雖然在游戲中是個(gè)身手敏捷的高手，但在現(xiàn)實(shí)中運(yùn)動(dòng)神經(jīng)特別遲鈍，每秒種只有在移動(dòng)不超過一米的范圍內(nèi)接住墜落的餡餅。現(xiàn)在給這條小徑如圖標(biāo)上坐標(biāo)： 為了使問題簡(jiǎn)化，假設(shè)在接下來的一段時(shí)間里，餡餅都掉落在0-10這11個(gè)位置。開始時(shí)gameboy站在5這個(gè)位置，因此在第一秒，他只能接到4,5,6這三個(gè)位置中期中一個(gè)位置上的餡餅。問gameboy最多可能接到多少個(gè)餡餅？（假設(shè)他的背包可以容納無窮多個(gè)餡餅） #include 7.課后作業(yè) 杭電ACM 1003、1466、1087、1159、1176、1058、1069、2059、2084 課文題目中的標(biāo)點(diǎn) 我們學(xué)習(xí)的課文中，好些題目上有標(biāo)點(diǎn)符號(hào)，它們大致可分為以下幾種： 一、引用文中的一句話 如《“你們想錯(cuò)了”》、《“兄弟便是朱德”》、《“我是你的兒子”》這三篇課文的題目是直接引用文中的一句話，因此加上了引號(hào)。 二、表示語(yǔ)句的停頓 課文題目中如有停頓，必須用逗號(hào)隔開，如《再見了，親人》、《別了，我愛的中國(guó)》、《火警，119》、《祖國(guó)，我終于回來了》、《延安，我把你追尋》等。 三、表示某種特殊語(yǔ)意 題目中有某種特殊語(yǔ)意時(shí)，也常用引號(hào)，如《“私塾先生”》、《我的“自白”書》等。其中的“私塾先生”指的是陳毅同志。 作業(yè) 1 1 動(dòng)態(tài)規(guī)劃練習(xí)： 為保證某一設(shè)備的正常運(yùn)轉(zhuǎn)，需備有三種不同的零件 E 1 , E 2, E 3 。若增加備用零件的數(shù)量，可提高設(shè)備正常運(yùn)轉(zhuǎn)的可靠性，但增加了費(fèi)用，而投資額僅為8000 元。已知備用零件數(shù)與它的可靠性和費(fèi)用的關(guān)系如表1 所示。 現(xiàn)要求在既不超出投資額的限制，又能盡量提高設(shè)備運(yùn)轉(zhuǎn)的可靠性的條件下，問各種零件的備件數(shù)量應(yīng)是多少為好？要寫出計(jì)算程序。 解： 設(shè)投資順序?yàn)?E1，E2，E3，階段編號(hào)逆向編號(hào)，即第一階段計(jì)算給E3 投資的效果。設(shè)ks 為第 k 階段的剩余款，kx 為第 k 階段的撥款額，狀態(tài)轉(zhuǎn)移方程為k k kx s s ? ??1，目標(biāo)函數(shù)為)1()1()1(max3 2 1P P P f ? ? ? ? ? ? ,其中1P，2P，3P 分別為 E1，E2，E3 增加的可靠性 第一階段：對(duì) E3 的投資效果 決策表： s1x1 0 2 3 4 *1x f1 0 1 0 1 1 1 0 1 2 1 1.1 1.1 3 1 1.1 1.21.2 4 1 1.1 1.2 1.7 4 1.7 1 1.1 1.2 1.7 4 1.7 6 1 1.1 1.2 1.7 4 1.7 7 1 1.1 1.2 1.7 4 1.7 8 1 1.1 1.2 1.7 4 1.7 第二階段，對(duì) E2 的投資效果 由于 E1 最多只需 3000，故 52?? s 千 決策表： s2x2 0 3 5 6 *2x f2 5 1.7 1.32 1.51.5 6 1.7 1.44 1.5 1.9 6 1.9 7 1.7 2.04 1.65 1.9 3 2.04 8 1.7 2.04 1.8 2.09 6 2.09 第三階段：對(duì) E1 的投資效果 決策表: s3x3 0 2 3 4 *3x R3 8 2.09 2.09 1.8 0.7 0,2 2.09 回溯：有兩組最優(yōu)解(1)x3=0,x2=3,x1=2,maxf=2.09(2)x3=1,x2=3,x1=0,maxf=2.092 層次分析法練習(xí)：你已經(jīng)去過幾家主要的摩托車商店，基本確定將從三種車型 中選購(gòu)一種，你選擇的標(biāo)準(zhǔn)主要有：價(jià)格、耗油量大小、舒適程度和外觀美觀情況。經(jīng)反復(fù)思考比較，構(gòu)造了它們之間的成對(duì)比較判斷矩陣。 三種車型（記為 a , b , c）關(guān)于價(jià)格、耗油量、舒適程度和外表美觀情況的成對(duì)比較判斷矩陣為： （1）根據(jù)上述矩陣可以看出四項(xiàng)標(biāo)準(zhǔn)在你心目中的比重是不同的，請(qǐng)按由重到輕順序?qū)⑺鼈兣懦觥?/p> （2）哪輛車最便宜、哪輛車最省油、哪輛車最舒適、哪輛車最漂亮？（3）用層次分析法確定你對(duì)這三種車型的喜歡程度（用百分比表示）。 解： (1)由重到輕依次是價(jià)格、耗油量、舒適程度和外表美觀情況(2)C 車最便宜，A 車最省油，A 車最舒適，B 車最漂亮(3)a、建立層次模型： 目標(biāo)層：選擇哪種車 準(zhǔn)則層：價(jià)格 耗油情況 舒適度 外表美觀度 方案層：A 車型 B 車型 C 車型 b、成對(duì)比較陣題目當(dāng)中已給出 c、計(jì)算權(quán)向量并做一致性檢驗(yàn) 運(yùn)行結(jié)果得到權(quán)向量為 w=(0.5820,0.2786,0.0899,0.0495),CR=0.0734<0.1,通過一致性檢驗(yàn) d、計(jì)算組合權(quán)向量。 由運(yùn)行結(jié)果得知方案層對(duì)目標(biāo)層的權(quán)重向量為（0.4091，0.4416，0.1493） 則可得出結(jié)論應(yīng)該選購(gòu) B 車型 附（代碼）： clc a=[1,3,7,8 1/3,1,5,5 1/7,1/5,1,3 1/8,1/5,1/3,1];%一致矩陣 [x,y]=eig(a);eigenvalue=diag(y);lamda=max(eigenvalue);ci1=(lamda-4)/3;cr1=ci1/0.9 w1=x(:,1)/sum(x(:,1))b1=[1,2,3;1/2,1,2;1/3,1/2,1];[x,y]=eig(b1);eigenvalue=diag(y);lamda=eigenvalue(1);ci21=(lamda-3)/2;cr21=ci21/0.58 w21=x(:,1)/sum(x(:,1))b2=[1 1/5 1/2;5 7;2 1/7 1];[x,y]=eig(b2);eigenvalue=diag(y);lamda=eigenvalue(1);ci22=(lamda-3)/2;cr22=ci22/0.58 w22=x(:,1)/sum(x(:,1))b3=[1 5;1/3 4;1/5 1/4 1];[x,y]=eig(b3);eigenvalue=diag(y);lamda=eigenvalue(1);ci23=(lamda-3)/2;cr23=ci23/0.58 w23=x(:,1)/sum(x(:,1))b4=[1 1/5 3;5 7;1/3 1/7 1];[x,y]=eig(b4);eigenvalue=diag(y);lamda=eigenvalue(1);ci24=(lamda-3)/2;cr24=ci24/0.58 w24=x(:,1)/sum(x(:,1))w_sum=[w21,w22,w23,w24]*w1 ci=[ci21,ci22,ci23,ci24];cr=ci*w1/sum(0.58*w1) 正確使用標(biāo)題中的標(biāo)點(diǎn)？ 學(xué)生在寫文章時(shí)，僅做到在文內(nèi)正確使用標(biāo)點(diǎn)符號(hào)是遠(yuǎn)遠(yuǎn)不夠的。我在教學(xué)中發(fā)現(xiàn)，一些學(xué)生在文章標(biāo)題中有濫用標(biāo)點(diǎn)的現(xiàn)象。因此，教師應(yīng)在文章標(biāo)題中如何使用標(biāo)點(diǎn)上對(duì)學(xué)生做正確引導(dǎo)。 一、文章題目是單句時(shí)，句末不用句號(hào) 例：在山的那邊 二、文章題目是復(fù)句時(shí)，中間可用逗號(hào)，句末不用句號(hào) 例：十年，還一副尊嚴(yán) 三、題目表疑問語(yǔ)氣的用問號(hào)，表感嘆語(yǔ)氣的用嘆號(hào) 例：還有人活著嗎？ 短些，再短些！ 四、題目中有停頓語(yǔ)氣的，可用以下方法處理 (1)用逗號(hào)、頓號(hào)或間隔號(hào) 例：啊，金色的秋天 黨在農(nóng)村的方針、政策、法規(guī) 夏夜·秋色 (2)“空格”表示停頓 例：關(guān)注學(xué)校關(guān)注家庭 (3)分行排列表語(yǔ)氣停頓 例：鍛煉心理品質(zhì) 培育健康心理 五、根據(jù)標(biāo)題內(nèi)容，也可用其它符號(hào)(如引號(hào)、破折號(hào)、省略號(hào)、書名號(hào)等等) 例：“諾曼底”號(hào)遇難記 下輩子，我們還當(dāng)母子 一位痛失兒子的母親自述 風(fēng)乍起…… 徐霞客和《徐霞客游記》 承德縣第二中學(xué) 李桂琴 五道河中心校包軍第二篇：動(dòng)態(tài)規(guī)劃教案
第三篇：課文題目中的標(biāo)點(diǎn)
第四篇：動(dòng)態(tài)規(guī)劃作業(yè)
第五篇：文章題目中的標(biāo)點(diǎn)符號(hào)
點(diǎn)擊咨詢 