動態(tài)規(guī)劃解決算法背包問題實(shí)驗(yàn)報(bào)告含源代碼

西安郵電大學(xué)（計(jì)算機(jī)學(xué)院）課內(nèi)實(shí)驗(yàn)報(bào)告實(shí)驗(yàn)名稱：動態(tài)規(guī)劃專業(yè)名稱：計(jì)算機(jī)科學(xué)與技術(shù)班級：學(xué)生姓名：學(xué)號（8位）：指導(dǎo)教師：實(shí)驗(yàn)日期：2023年5月9日實(shí)驗(yàn)?zāi)康募皩?shí)驗(yàn)環(huán)境使用動態(tài)規(guī)劃法和回溯法生成兩個長字符串的最優(yōu)化比對結(jié)果通過實(shí)際案例，領(lǐng)略算法的執(zhí)行效率。掌握動態(tài)規(guī)劃、貪心算法、回溯法、分支限界法的原理，并可以按其原理編程實(shí)現(xiàn)解決0-1背包問題，以加深對上述方法的理解。實(shí)驗(yàn)環(huán)境：VisualC++6.0二.實(shí)驗(yàn)內(nèi)容1.設(shè)計(jì)一個O（n^2）時(shí)間的算法，找出由n個數(shù)組成的序列的最長單調(diào)遞增子序列2.將算法分析題3—1中算法的計(jì)算時(shí)間減至O（nlogn）3.給定n種物品和一個背包。物品i的重量是，其價(jià)值為，背包容量為C。問應(yīng)當(dāng)如何選擇裝入背包的物品，使得裝入背包中物品的總價(jià)值最大？三．方案設(shè)計(jì)1.動態(tài)規(guī)劃的一個計(jì)算兩個序列的最長公共子序列的方法如下：以兩個序列X、Y為例子：設(shè)有二維數(shù)組f[i,j]表達(dá)X的i位和Y的j位之前的最長公共子序列的長度，則有：f[1][1]=same(1,1);f[i,j]=max{f[i-1][j-1]+same(i,j),f[i-1,j],f[i,j-1]}其中，same(a,b)當(dāng)X的第a位與Y的第b位相同時(shí)為“1”，否則為“0”。此時(shí)，二維數(shù)組中最大的數(shù)便是X和Y的最長公共子序列的長度，依據(jù)該數(shù)組回溯，便可找出最長公共子序列。該算法的空間、時(shí)間復(fù)雜度均為O(n^2)，通過優(yōu)化后，空間復(fù)雜度可為O(n)。核心代碼：voidLCSL(intm,intn,int*x,int*y,intc[][N],intb[][N]){c[0][0]=0;inti,j;for(i=1;i<=m;i++)c[i][0]=0;for(i=1;i<=n;i++)c[0][i]=0;for(i=1;i<=m;i++)for(j=1;j<=m;j++){if(x[i]==y[j]){c[i][j]=c[i-1][j-1]+1;b[i][j]=1;}elseif(c[i-1][j]>=c[i][j-1]){c[i][j]=c[i-1][j];b[i][j]=2;}else{c[i][j]=c[i][j-1];b[i][j]=3;}}cout<<c[m][m]<<endl;}voidLCS(inti,intj,int*x,intb[][N]){if(i==0||j==0)return;if(b[i][j]==1){LCS(i-1,j-1,x,b);for(inty=1;y<i;y++)if(x[y]==x[i])return;cout<<x[i]<<"";}elseif(b[i][j]==2){LCS(i-1,j,x,b);}elseLCS(i,j-1,x,b);}voidQuickSort(inta[],intp,intr){if(p<r){intq=Partition(a,p,r);QuickSort(a,p,q-1);//對左半段排序QuickSort(a,q+1,r);//對右半段排序}}通過動態(tài)規(guī)劃求出最長公共子序列，再用任意排序算法，得出最長單調(diào)遞增序列，我選用的排序方法是快速排序。一個長度為i的候選子序列的最后一個元素至少與一個長度為i-1的候選子序列的最后一個元素同樣大，通過只想輸入序列中元素的指針來維持候選子序列。3.0/1背包問題:現(xiàn)有n種物品，對1<=i<=n，第i種物品的重量為正整數(shù)Wi，價(jià)值為正整數(shù)Vi，背包能承受的最大載重量為正整數(shù)C，現(xiàn)規(guī)定找出這n種物品的一個子集，使得子集中物品的總重量不超過C且總價(jià)值盡量大。動態(tài)規(guī)劃算法描述:根據(jù)問題描述，可以將其轉(zhuǎn)化為如下的約束條件和目的函數(shù)：尋找一個滿足約束條件，并使目的函數(shù)式達(dá)成最大的解向量，使得，并且達(dá)成最大。0-1背包問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)。假設(shè)是所給的問題的一個最優(yōu)解，則是下面問題的一個最優(yōu)解：。假如不是的話，設(shè)是這個問題的一個最優(yōu)解，則，且。因此，，這說明是所給的0-1背包問題比更優(yōu)的解，從而與假設(shè)矛盾。按照上面的情況，可以得到遞推公式：設(shè)最優(yōu)值為m(i,j)。 max{m(i+1,j),m(i+1,j-)+}m(i,j)= m(i+1,j) m(n,j)=0#include<stdio.h>intV[200][200];//前i個物品裝入容量為j的背包中獲得的最大價(jià)值intmax(inta,intb){if(a>=b)returna;elsereturnb;}intKnapSack(intn,intw[],intv[],intx[],intC){inti,j;for(i=0;i<=n;i++)V[i][0]=0;for(j=0;j<=C;j++)V[0][j]=0;for(i=0;i<=n-1;i++)for(j=0;j<=C;j++)if(j<w[i])V[i][j]=V[i-1][j];elseV[i][j]=max(V[i-1][j],V[i-1][j-w[i]]+v[i]); j=C;for(i=n-1;i>=0;i--){if(V[i][j]>V[i-1][j]){x[i]=1;j=j-w[i];}elsex[i]=0;}printf("選中的物品是:\n");for(i=0;i<n;i++)printf("%d",x[i]);printf("\n");returnV[n-1][C];}voidmain(){ints;//獲得的最大價(jià)值intw[15];//物品的重量intv[15];//物品的價(jià)值intx[15];//物品的選取狀態(tài)intn,i;intC;//背包最大容量n=5;printf("請輸入背包的最大容量:\n");scanf("%d",&C);printf("輸入物品數(shù):\n");scanf("%d",&n);printf("請分別輸入物品的重量:\n");for(i=0;i<n;i++)scanf("%d",&w[i]);printf("請分別輸入物品的價(jià)值:\n");for(i=0;i<n;i++)scanf("%d",&v[i]);s=KnapSack(n,w,v,x,C);printf("最大物品價(jià)值為:\n");printf("%d\n",s);}運(yùn)營結(jié)果1.2.3.五．心得體會通過這次實(shí)驗(yàn)，對動態(tài)規(guī)劃法求最長公共子序列有更深的理解。其實(shí)無非就是抓住書上的遞推公式進(jìn)行寫，動態(tài)規(guī)劃依賴于上一個或者上一行的解，就是在