動態(tài)規(guī)劃算法及其應(yīng)用

1、湖州師范學(xué)院實驗報告課程名稱：算法實驗二：動態(tài)規(guī)劃方法及其應(yīng)用一、實驗?zāi)康?、掌握動態(tài)規(guī)劃方法的基本思想和算法設(shè)計的基本步驟。2、應(yīng)用動態(tài)規(guī)劃方法解決實際問題。二、實驗內(nèi)容1、問題描述1)背包問題給定N種物品和一個背包。物品i的重量是Ci，價值為Wi；背包的容量為V。問應(yīng)如何選擇裝入背包中的物品，使得裝入背包中物品的總價值最大？在選擇裝入背包的物品，對每種物品只有兩個選擇：裝入或不裝入，且不能重復(fù)裝入。輸入數(shù)據(jù)的第一行分別為：背包的容量V,物品的個數(shù)N。接下來的N行表示N個物品的重量和價值。輸出為最大的總價值。2)矩陣連乘問題給定n個矩陣:Al,A2,.,An,其中Ai與Ai+1是可乘的，i=

2、l，2.，n-1。確定計算矩陣連乘積的計算次序，使得依此次序計算矩陣連乘積需要的數(shù)乘次數(shù)最少。輸入數(shù)據(jù)為矩陣個數(shù)和每個矩陣規(guī)模，輸出結(jié)果為計算矩陣連乘積的計算次序和最少數(shù)乘次數(shù)。3)LCS問題給定兩個序列，求最長的公共子序列及其長度。輸出為最長公共子序列及其長度。2、數(shù)據(jù)輸入：文件輸入或鍵盤輸入。3、要求：1) 完成上述兩個問題，時間為2次課。2) 獨立完成實驗及實驗報告。三、實驗步驟1、理解方法思想和問題要求。2、采用編程語言實現(xiàn)題目要求。3、上機輸入和調(diào)試自己所寫的程序。4、附程序主要代碼：(1)#include<stdio.h>intmax(inta,intb)return(

3、a>b)?a:b;intknapSack(intW,intwt,intval,intn)if(n=0|W=0)return0;if(wtn-1>W)returnknapSack(W,wt,val,n-1);elsereturnmax(valn-1+knapSack(W-wtn-1,wt,val,n-1),knapSack(W,wt,val,n-1);intmain()intval=60,100,120;intwt=10,20,30;intW=50;intn=sizeof(val)/sizeof(val0);printf("%d",knapSack(W,wt,va

4、l,n);return0;(2)#include<stdio.h>#include<iostream>usingnamespacestd;constintL=7;intMatrixChain(intn,int*m,int*s,int*p);voidTraceback(inti,intj,int*s);intmain()intpL=30,35,15,5,10,20,25;int*s=newint*L;int*m=newint*L;for(inti=0;i<L;i+)si=newintL;mi=newintL;cout"矩陣的最少計算次數(shù)為："Ma

5、trixChain(6,m,s,p)endl；cout"矩陣最優(yōu)計算次序為："endl；Traceback(1,6,s)；return0；intMatrixChain(intn,int*m,int*s,int*p)for(inti=1；i=n；i+)mii=0；for(intr=2;r<=n;r+)for(inti=1;i<=n-r+1;i+)intj=i+r-1;mij=mi+1j+pi-1*pi*pj;sij=i;for(intk=i+1;k<j;k+)intt=mik+mk+1j+pi-1*pk*pj;if(t<mij)mij=t;sij=k;

6、returnm1L-1;voidTraceback(inti,intj,int*s)if(i=j)return;Traceback(i,sij,s);Traceback(sij+1,j,s);cout<<"MultiplyA"<<i<<","<<sij;cout<<"andA"<<(sij+1)<<","<<j<<endl;(3)#include<bits/stdc+.h>intmax(inta,

7、intb);intlcs(char*X,char*Y,intm,intn)if(m=0|n=0)return0;if(Xm-1=Yn-1)return1+lcs(X,Y,m-1,n-1);elsereturnmax(lcs(X,Y,m,n-1),lcs(X,Y,m-1,n);intmax(inta,intb)return(a>b)?a:b;intmain()charX="AGGTAB"charY="GXTXAYB"intm=strlen(X);intn=strlen(Y);printf("LengthofLCSis%dn",lc

8、s(X,Y,m,n);return0;5、實驗結(jié)果：(1)i.3Eec01背包問趣曲呂220Process曰？iitd日Qsecondswithreturnvslue0請按任意鍵繼綾.i»sslr：15125JIultiplyA2,2andA3,3血ItiplyAL,1andA2,3Multiply止4,4andAS,5Multiply止4,5andA6,6MultiplyAl,3and扎4,6Processexitedafter0.4055secondswithreturnvalue0青按任意鍵継續(xù)(3)EJE：1亂叭最E公共子序？11啟畑LengthofLCSis4Process

9、editedafter002448secondswithreturnvalue0青按任意鍵繼續(xù).四、實驗分析1、01背包問題分析：第一，包的容量比該商品體積小，裝不下，此時的價值與前卜1個的價值是一樣的，即V(i,j)=V(i-1,j)；第二，還有足夠的容量可以裝該商品，但裝了也不一定達到當(dāng)前最優(yōu)價值，所以在裝與不裝之間選擇最優(yōu)的一個，即Val(i,j)=maxVal(i-1,j),Val(i-1,j-wal(i)+val(i)其中V(i-1,j)表示不裝，Val(i-1,j-wt(i)+val(i)表示裝了第i個商品，背包容量減少wt(i)但價值增加了val(i)；由此可以得出遞推關(guān)系式：1

10、) jvwt(i)Val(i,j)=Val(i-1,j)2) j>=wt(i)Val(i,j)=maxVal(i-1,j),Val(i-1,j-wt(i)+val(i)核心代碼：intknapSack(intW,intwt,intval,intn)if(n=0|W=0)return0;if(wtn-1>W)returnknapSack(W,wt,val,n-1);elsereturnmax(valn-1+knapSack(W-wtn-1,wt,val,n-1),knapSack(W,wt,val,n-1);2、矩陣連乘問題分析：計算矩陣連乘乘積A1A2A3A4A5A6，其中各矩陣的維數(shù)分別是：A1：30*35；A2：35*15；A3：15*5；A4：5*10；A5：10*20；A6：20*25設(shè)計算Ai：j,lWiWjWn，所需要的最少數(shù)乘次數(shù)mi,j,則原問題的最優(yōu)值為m1,n。當(dāng)i=j時，Ai：j=Ai，因此，mii=0，i=1,2,，n當(dāng)i<j時，若Ai：j的最優(yōu)次序在Ak和Ak+1之間斷開，i二