算法分析與設(shè)計(jì)課設(shè)

1、日期成績(jī)?cè)u(píng)定表學(xué)生姓名班級(jí)學(xué)號(hào)專業(yè)課程設(shè)計(jì)題目動(dòng)態(tài)規(guī)劃-k乘積問(wèn)題回溯法-最小重量機(jī)器問(wèn)題評(píng)語(yǔ)組長(zhǎng)簽字：成績(jī)20年月日課程設(shè)計(jì)任務(wù)書(shū)學(xué)院專業(yè)學(xué)生姓名班級(jí)學(xué)號(hào)課程設(shè)計(jì)題目動(dòng)態(tài)規(guī)劃-k乘積問(wèn)題回溯法-最小重量機(jī)器問(wèn)題實(shí)踐教學(xué)要求與任務(wù)：要求：1 .鞏固和加深對(duì)基本算法的理解和運(yùn)用，提高綜合運(yùn)用課程知識(shí)進(jìn)行算法設(shè)計(jì)與分析的能力。2 .培養(yǎng)學(xué)生自學(xué)參考書(shū)籍，查閱手冊(cè)、和文獻(xiàn)資料的能力。3 .通過(guò)實(shí)際課程設(shè)計(jì)，掌握利用動(dòng)態(tài)規(guī)劃算法、回溯法、分支限界法等算法的基本思想，并能運(yùn)用這些方法設(shè)計(jì)算法并編寫(xiě)程序解決實(shí)際問(wèn)題。4 .了解與課程有關(guān)的知識(shí)，能正確解釋和分析實(shí)驗(yàn)結(jié)果。任務(wù)：按照算法設(shè)計(jì)方法和原理，設(shè)計(jì)算

2、法，編寫(xiě)程序并分析結(jié)果，完成如下內(nèi)容：1 .運(yùn)用動(dòng)態(tài)規(guī)劃算法求解k乘積問(wèn)題。2 .運(yùn)用回溯法求解最小重量機(jī)器問(wèn)題。工作計(jì)劃與進(jìn)度安排：3 11周：查閱資料。掌握算法設(shè)計(jì)思想，進(jìn)行算法設(shè)計(jì)。4 12周：算法實(shí)現(xiàn)，調(diào)試程序并進(jìn)行結(jié)果分析。撰寫(xiě)課程設(shè)計(jì)報(bào)告，驗(yàn)收與答辯。指導(dǎo)教師：201年月日專業(yè)負(fù)責(zé)人：201年月日學(xué)院教學(xué)副院長(zhǎng)：201年月日摘要為了滿足人們對(duì)大數(shù)據(jù)量信息處理的渴望，為解決各種實(shí)際問(wèn)題，計(jì)算機(jī)算法學(xué)得到了飛速的發(fā)展，線性規(guī)劃、動(dòng)態(tài)規(guī)劃、貪心策略等一系列運(yùn)籌學(xué)模型紛紛運(yùn)用到計(jì)算機(jī)算法學(xué)中，產(chǎn)生了解決各種現(xiàn)實(shí)問(wèn)題的有效算法。雖然設(shè)計(jì)一個(gè)好的求解算法更像是一門藝術(shù)而不像是技術(shù)，但仍然存在一

3、些行之有效的、能夠用于解決許多問(wèn)題的算法設(shè)計(jì)方法，你可以使用這些方法來(lái)設(shè)計(jì)算法，并觀察這些算法是如何工作的。一般情況下，為了獲得較好的性能，必須對(duì)算法進(jìn)行細(xì)致的調(diào)整。但是在某些情況下，算法經(jīng)過(guò)調(diào)整之后性能仍無(wú)法達(dá)到要求，這時(shí)就必須尋求另外的方法來(lái)求解該問(wèn)題。動(dòng)態(tài)規(guī)劃的基本思想與分治法類似，也是將待求解的問(wèn)題分解成若干份的子問(wèn)題，先分別解決好子問(wèn)題，然后從子問(wèn)題中得到最終解。但動(dòng)態(tài)規(guī)劃中的子問(wèn)題往往不是相互獨(dú)立的，而是彼此之間有影響，因?yàn)橛行┳訂?wèn)題可能要重復(fù)計(jì)算多次，所以利用動(dòng)態(tài)規(guī)劃使這些子問(wèn)題只計(jì)算一次?；厮莘ㄔ谟脕?lái)求問(wèn)題的所有解時(shí)，要回溯到根，且根結(jié)點(diǎn)的所有可行的子樹(shù)都已被搜索遍才結(jié)束。而回

4、溯法在用來(lái)求問(wèn)題的任一解時(shí)，只要搜索到問(wèn)題的一個(gè)解就可以結(jié)束。這就是以深度優(yōu)先的方式系統(tǒng)地搜索問(wèn)題解的回溯算法，它適用于解決一些類似n皇后問(wèn)題等求解方案問(wèn)題，也可以解決一些最優(yōu)化問(wèn)題。在做題時(shí)，有時(shí)會(huì)遇到這樣一類題目，它的問(wèn)題可以分解，但是又不能得出明確的動(dòng)態(tài)規(guī)劃或是遞歸解法，此時(shí)可以考慮用回溯法解決此類問(wèn)題。回溯法的優(yōu)點(diǎn)在于其程序結(jié)構(gòu)明確，可讀性強(qiáng)，易于理解，而且通過(guò)對(duì)問(wèn)題的分析可以大大提高運(yùn)行效率。關(guān)鍵詞：算法；動(dòng)態(tài)規(guī)劃；回溯法;目錄、問(wèn)題描述11.1 k乘積問(wèn)題11.2 最小重量機(jī)器問(wèn)題1二、算法設(shè)計(jì)1三、設(shè)計(jì)原理23.1 動(dòng)態(tài)規(guī)劃23.2 回溯法2四、問(wèn)題分析與設(shè)計(jì)34.1 k乘積問(wèn)題

5、34.2 最小重量機(jī)器設(shè)計(jì)問(wèn)題4五、算法實(shí)現(xiàn)45.1 k乘積問(wèn)題45.2 最小重量機(jī)器問(wèn)題7六、結(jié)果分析10總結(jié)11參考文獻(xiàn)12、問(wèn)題描述1.1 k乘積問(wèn)題設(shè)I是一個(gè)n位十進(jìn)制整數(shù)。如果將I劃分為k段，則可得到k個(gè)整數(shù)。這k個(gè)整數(shù)的乘積稱為I的一個(gè)k乘積，試設(shè)計(jì)一個(gè)算法，對(duì)于給定的I和k,求出I的最大k乘積。1.2 最小重量機(jī)器問(wèn)題設(shè)某一機(jī)器由n個(gè)部件組成，每一種部件都可以從m個(gè)不同的供應(yīng)商處購(gòu)得。設(shè)wij是從供應(yīng)商j處購(gòu)得的部件i的重量，cij是相應(yīng)的價(jià)格。試設(shè)計(jì)一個(gè)算法，給出總價(jià)格不超過(guò)c的最小重量機(jī)器設(shè)計(jì)。二、算法設(shè)計(jì)1 .對(duì)于給定的I和k,計(jì)算I的最大k乘積。2 .對(duì)于給定的機(jī)器部件重

6、量和機(jī)器部件價(jià)格，計(jì)算總價(jià)格不超過(guò)d的最小重量機(jī)器設(shè)計(jì)。三、設(shè)計(jì)原理3.1動(dòng)態(tài)規(guī)劃動(dòng)態(tài)規(guī)劃的基本思想是將問(wèn)題分解為若干個(gè)小問(wèn)題，解子問(wèn)題，然后從子問(wèn)題得到原問(wèn)題的解。設(shè)計(jì)動(dòng)態(tài)規(guī)劃法的步驟：(1)找出最優(yōu)解的性質(zhì)，并刻畫(huà)其結(jié)構(gòu)特征；(2)遞歸地定義最優(yōu)值(寫(xiě)出動(dòng)態(tài)規(guī)劃方程)；(3)以自底向上的方式計(jì)算出最優(yōu)值；(4)根據(jù)計(jì)算最優(yōu)值時(shí)得到的信息，構(gòu)造一個(gè)最優(yōu)解。3.2回溯法回溯法是一個(gè)既帶有系統(tǒng)性又帶有跳躍性的的搜索算法。它在包含問(wèn)題的所有解的解空間樹(shù)中，按照深度優(yōu)先的策略，從根結(jié)點(diǎn)出發(fā)搜索解空間樹(shù)。算法搜索至解空間樹(shù)的任一結(jié)點(diǎn)時(shí)，總是先判斷該結(jié)點(diǎn)是否肯定不包含問(wèn)題的解。如果肯定不包含，則跳過(guò)對(duì)以

7、該結(jié)點(diǎn)為根的子樹(shù)的系統(tǒng)搜索，逐層向其祖先結(jié)點(diǎn)回溯。否則，進(jìn)入該子樹(shù)，繼續(xù)按深度優(yōu)先的策略進(jìn)行搜索。回溯法在用來(lái)求問(wèn)題的所有解時(shí)，要回溯到根，且根結(jié)點(diǎn)的所有子樹(shù)都已被搜索遍才結(jié)束。而回溯法在用來(lái)求問(wèn)題的任一解時(shí)，只要搜索到問(wèn)題的一個(gè)解就可以結(jié)束。這種以深度優(yōu)先的方式系統(tǒng)地搜索問(wèn)題的解的算法稱為回溯法，它適用于解一些組合數(shù)較大的問(wèn)題。四、問(wèn)題分析與設(shè)計(jì)4.1k乘積問(wèn)題1 .分析最優(yōu)解的結(jié)構(gòu)為了方便起見(jiàn)，設(shè)I(s,t)是I的由s位開(kāi)始的t位數(shù)字組成的十進(jìn)制數(shù)，R(i,j)表示I(0,i)的j乘積。第j段的起始位置為第w位,1<w<j。則有如下關(guān)系R(i,j)=R(i,j-1)xI(w,j

8、-w)要使R(i,j)最大，則R(i,j-1)也是最大，所以最大K乘積問(wèn)題的最優(yōu)解包含其子問(wèn)題的最優(yōu)解。2 .建立遞歸關(guān)系設(shè)MaxIij表示I(0,i)的最大j乘積，則原問(wèn)題的最優(yōu)值為MaxInk。當(dāng)k=1時(shí)，MaxIn1=I(0,n);當(dāng)k*1時(shí)，可利用最優(yōu)子結(jié)構(gòu)性質(zhì)計(jì)算MaxInk,若計(jì)算MaxInk的第k段的起始位置為第w位，1<w<j,則有MaxInk=MaxIwk-1xI(w,n-w)。由于在計(jì)算時(shí)并不知道第k段的起始位置w,所以w還未定。不過(guò)w的值只有n-k+2種可能，即k-1&w<n。所以MaxInk可以遞歸地定義為I(0,n)k=1MaxInk=max

9、MaxIwk-1xI(w,n-w)kw1MaxInk給出了最優(yōu)值，同時(shí)還確定了計(jì)算最優(yōu)的斷開(kāi)位置w,也就時(shí)說(shuō)，對(duì)于這個(gè)w有MaxInk=MaxIwk-1xI(w,n-w)若將對(duì)應(yīng)于MaxInk的斷開(kāi)位置w記為demarcationnk后，可遞歸地由demarcationnk構(gòu)造相應(yīng)的最優(yōu)解。3 .2最小重量機(jī)器設(shè)計(jì)問(wèn)題1.用遞歸函數(shù)backtrack(i)來(lái)實(shí)現(xiàn)回溯法搜索排列樹(shù)(形式參數(shù)i表示遞歸深度)。若cp>d,則為不可行解，剪去相應(yīng)子樹(shù)，返回到i-1層繼續(xù)執(zhí)行。若cw>=weight,則不是最優(yōu)解，剪去相應(yīng)子樹(shù)，返回到i-1層繼續(xù)執(zhí)行。若i>n,則算法搜索到一個(gè)葉結(jié)點(diǎn)，

10、用weight對(duì)最優(yōu)解進(jìn)行記錄，返回到i-1層繼續(xù)執(zhí)行；用for循環(huán)對(duì)部件i從m個(gè)不同的供應(yīng)商購(gòu)得的情況進(jìn)行選擇(1&j&m,2.主函數(shù)調(diào)用一次backtrack(l)即可完成整個(gè)回溯搜索過(guò)程，最終得到的weight即為所求最小總重量，p為該機(jī)器最小重量的價(jià)格。五、算法實(shí)現(xiàn)5.1k乘積問(wèn)題#include<stdio.h>#include<string.h>#include<stdlib.h>#defineMAXN51#defineMAXK10/mij表示1i十進(jìn)制位分成j段所得的最大乘積longmMAXKMAXN尸0,0;/wij表示ij十

11、進(jìn)制位所組成的十進(jìn)制數(shù)longwMAXNMAXN=0,0;intleafMAXNMAXN=0,0;voidmaxdp(intn,intk,int*a)inti,j,d;longtemp,max;for(i=1;i<=n;i+)分成一段mi1=w1i;for(i=2;i<=n;i+)/DP過(guò)程for(j=2;j<=k;j+)max=0;for(d=1;d<i;d+)/Testprintf("%d*%d=%ldt",mdj-1,wd+1i,mdj-1*wd+1i);if(temp=mdj-1*wd+1i)>max)max=temp;leafij=d

12、;mij=max;printf("n");printf("n");for(i=1;i<=n;i+)for(j=1;j<=n;j+)printf("%ldt",mij);printf("n");printf("n");for(i=1;i<=n;i+)for(j=1;j<=n;j+)printf("%ldt",leafij);printf("n");/輸出分割后的K個(gè)數(shù)voidprint_foot(int*data,intn,intk)

13、intd,i;intstack256;inttop=0;inttmp;tmp=n;while(tmp=leaftmpk)>0)stacktop+=tmp;k-;printf("Dividedsequence:n");i=1;while(-top)>=0)tmp=stacktop;for(;i<=tmp;i+)printf("%d",datai);printf("");for(;i<=n;i+)printf("%d",datai);printf("n");intmain(v

14、oid)intn,k,i,j;intaMAXN=0,la=0;charc;scanf("%d%d",&n,&k);/inputn,kwhile(c=getchar()!='#')/readintegera+la=c-'0'for(i=1;i<=n;i+)wii=ai;for(j=i+1;j<=n;j+)wij=wij-1*10+aj;for(i=1;i<=n;i+)for(j=1;j<=n;j+)printf("%ldt",wij);printf("n");max

15、dp(n,k,a);printf("%ldn",mnk);print_foot(a,n,k);return0;5.2最小重量機(jī)器問(wèn)題/*頭文件最小重量機(jī)器設(shè)計(jì)問(wèn)題.h*/#ifndefKNAP_H#defineKNAP_H#include<iostream>#include<fstream>usingnamespacestd;classMachinepublic:Machine(char*in,char*out);Machine();voidSolve();protected:voidSearch(inti,ints,intl,int*e);void

16、Print();private:intn;intm;intd;int*w;int*c;intmin;int*plan;ofstreamfout;#endif/*函數(shù)實(shí)現(xiàn)文件最小重量機(jī)器設(shè)計(jì)問(wèn)題.cpp*/#include"最小重量機(jī)器設(shè)計(jì)問(wèn)題.h"Machine:Machine(char*in,char*out):fout(out)ifstreamfin(in);if(!fin)機(jī)器類/構(gòu)造函數(shù)/析構(gòu)函數(shù)/輸出結(jié)果到文件/從第i個(gè)部件開(kāi)始遞歸搜索/輸出結(jié)果/部件個(gè)數(shù)/供應(yīng)商個(gè)數(shù)/價(jià)格上限/部件重量/部件價(jià)格/最小重量/選購(gòu)的部件/輸出結(jié)果文件cerr<<&quo

17、t;文件"<<in<<"無(wú)法打開(kāi)！"<<endl;exit(1);fin>>n>>m>>d;w=newint*n+1;/初始化部件個(gè)數(shù)n,供應(yīng)商數(shù)m,價(jià)格限制dfor(inti=1;i<=n;i+)wi=newintm+1;for(intj=1;j<=m;j+)fin>>wij;c=newint*n+1;for(inti=1;i<=n;i+)ci=newintn+1;for(intj=1;j<=m;j+)fin>>cij;fin.close();

18、min=INT_MAX;plan=newintn+1;for(inti=1;i<=n;i+)plani=0;if(!fout)/初始化部件重量/初始化部件價(jià)格/初始化最小重量/初始化選購(gòu)計(jì)劃cerr<<"文件"<<out<<"無(wú)法打開(kāi)！"<<endl;exit(1);Machine:Machine()if(fout)fout.close();for(inti=1;i<=n;i+)if(wi)delete口wi;if(ci)delete口ci;if(w)delete口w;if(c)delete口c

19、;voidMachine:Solve()int*e;e=newintn+1;for(inti=1;i<=n;i+)ei=0；Search。，0,0,e);第Print();voidMachine:Search(inti,ints,intl,int*e)if(i=n+1)if(s<min&&l<=d)min=s;for(inti=1;i<=n;i+)plani=ei;return;if(s>min)return;for(intj=1;j<=m;j+)ei=j;s+=w皿;1 +=c皿;Search(i+1,s,l,e);s-=wij;l-=ci

20、j;voidMachine:Print()fout<<min<<endl;for(inti=1;i<=n;i+)fout<<plani<<''/*主函數(shù)文件test.cpp*/#include"最小重量機(jī)器設(shè)計(jì)問(wèn)題.h"intmain()char*in="input.txt"char*out="output.txt"Machinemachine(in,out);machine.Solve();個(gè)零件開(kāi)始搜索，初始重量和價(jià)格是0輸出函數(shù)/選購(gòu)?fù)戤?找到一個(gè)更優(yōu)解/更新

21、重量最小值/更新選購(gòu)計(jì)劃/重量超過(guò)min,剪枝加上第i部件由j供應(yīng)商提供的重量加上第i部件由j供應(yīng)商提供的價(jià)格/遞歸選購(gòu)下一個(gè)部件/輸入文件/輸出文件/文件初始化機(jī)器/回溯法求解return0;六、結(jié)果分析1.*'C；UseriAdministratorDe5ktop機(jī)房軟件DubugCppl.exe"qa 0810010lasDivided sequence -5 21Pr-ess an u kgy tQ continue注釋：輸入一個(gè)三位數(shù)，將其分為兩段，使這兩端乘積最大當(dāng)這個(gè)三位數(shù)為521時(shí)，5與21相乘積最大，為105二）回2.32GH243S126S口平谷口聿后口毛后口鼻口口聿1d-電32 34上 1!巨< 爰-7|FJ一！-/-lbJdT1 -: .-t:>wplkYlH 1ITT JTT -/Ff .tn .H .Is -in ITF JT A JftlArA JlTJ o 7J 4%" TJ TJ制.I" 口田用古口田都e7口用剖.1 -: 口金 s 6 3 3 1 6! kl 1X1X1 vlxlck 113233113