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

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

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

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

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

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

6、對于給定的機(jī)器部件重量和機(jī)器部件價(jià)格，計(jì)算總價(jià)格不超過d的最小重量機(jī)器設(shè)計(jì)。三、設(shè)計(jì)原理3.1動(dòng)態(tài)規(guī)劃動(dòng)態(tài)規(guī)劃的基本思想是將問題分解為若干個(gè)小問題，解子問題，然后從子問題得到原問題的解。設(shè)計(jì)動(dòng)態(tài)規(guī)劃法的步驟： （1） 找出最優(yōu)解的性質(zhì)，并刻畫其結(jié)構(gòu)特征；（2）遞歸地定義最優(yōu)值（寫出動(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)性又帶有跳躍性的的搜索算法。它在包含問題的所有解的解空間樹中，按照深度優(yōu)先的策略，從根結(jié)點(diǎn)出發(fā)搜索解空間樹。算法搜索至解空間樹的任一結(jié)點(diǎn)時(shí)，總是先判斷該結(jié)點(diǎn)是否肯定不包含問題的解。如

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

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

9、-1wn。所以MaxInk可以遞歸地定義為I(0,n)                               k1MaxInk =max  MaxIwk-1×I(w,n-w)      

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

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

12、得的最大乘積long mMAXKMAXN=0,0 ;/wij表示ij十進(jìn)制位所組成的十進(jìn)制數(shù)long wMAXNMAXN=0,0 ;int leafMAXNMAXN = 0,0;void maxdp(int n,int k,int *a)int i,j,d;long temp,max;for(i=1; i<= n; i+) /分成一段 mi1 = w1i; for(i=2 ; i<= n ; i+) /DP 過程for(j=2; j<= k ; j+) max = 0;for(d=1; d < i ; d+)/Testprintf("%d*%d=%ldt -&

13、quot;,mdj-1,wd+1i,mdj-1*wd+1i);if ( (temp = mdj-1*wd+1i) > max)max = temp ;leafij=d;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(&

14、quot;%ldt",leafij);printf("n");/輸出分割后的K個(gè)數(shù)void print_foot(int *data, int n, int k)int d, i;int stack256;int top = 0;int tmp;tmp = n;while (tmp = leaftmpk) > 0)stacktop+ = tmp;k-;printf("Divided sequence:n");i = 1;while (-top) >= 0)tmp = stacktop;for ( ; i <= tmp; i+)

15、printf("%d", datai);printf(" ");for (; i <= n; i+)printf("%d", datai);printf("n");int main(void)int n,k,i,j;int aMAXN=0,la=0;char c ;scanf("%d %d ",&n,&k); /input n, kwhile ( ( c=getchar() )!='#') /read integera+la = c-'0'

16、;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"); maxdp(n,k,a) ;printf("%ldn",mnk) ;print_foot(a, n, k);return 0;5.2最小重量機(jī)器問題/*頭文件 最小重量機(jī)器設(shè)計(jì)問題.h*/#ifndef KNAP_H#define KNAP_

17、H#include <iostream>#include <fstream>using namespace std;class Machine/機(jī)器類public:Machine(char *in, char *out);/構(gòu)造函數(shù)Machine();/析構(gòu)函數(shù)void Solve();/輸出結(jié)果到文件protected:void Search(int i, int s, int l, int *e);/從第i個(gè)部件開始遞歸搜索void Print();/輸出結(jié)果private:int n;/部件個(gè)數(shù)int m;/供應(yīng)商個(gè)數(shù)int d;/價(jià)格上限int *w;/部件重量

18、int *c;/部件價(jià)格int min;/最小重量int *plan;/選購的部件ofstream fout;/輸出結(jié)果文件;#endif/*函數(shù)實(shí)現(xiàn)文件 最小重量機(jī)器設(shè)計(jì)問題.cpp*/#include "最小重量機(jī)器設(shè)計(jì)問題.h"Machine:Machine(char *in, char *out) : fout(out)ifstream fin(in);if( !fin )cerr << "文件" << in << "無法打開!" << endl;exit(1);fin >

19、> n >> m >> d;/初始化部件個(gè)數(shù)n，供應(yīng)商數(shù)m，價(jià)格限制dw = new int*n+1;for(int i = 1; i <= n; i+)wi = new intm+1;for(int j = 1; j <= m; j+)fin >> wij;/初始化部件重量c = new int*n+1;for(int i = 1; i <= n; i+)ci = new intn+1;for(int j = 1; j <= m; j+)fin >> cij;/初始化部件價(jià)格fin.close();min = IN

20、T_MAX;/初始化最小重量plan = new intn+1;for(int i = 1; i <= n; i+)plani = 0;/初始化選購計(jì)劃if( !fout )cerr << "文件" << out << "無法打開!" << endl;exit(1);Machine:Machine()if(fout)fout.close();for(int i = 1; i <= n; i+)if(wi)delete wi;if(ci)delete ci;if(w)delete w;if(c)d

21、elete c;void Machine:Solve()int *e;e = new intn+1;for(int i = 1; i <= n; i+)ei = 0;Search(1, 0, 0, e);/第一個(gè)零件開始搜索，初始重量和價(jià)格是0Print();/輸出函數(shù)void Machine:Search(int i, int s, int l, int *e)if(i = n+1)/選購?fù)戤卛f(s < min && l <= d)/找到一個(gè)更優(yōu)解min = s;/更新重量最小值for(int i = 1; i <= n; i+)plani = ei;/更新選購計(jì)劃return;if(s > min)/重量超過min，剪枝 return;for(int j = 1; j <= m; j+)ei = j;s += wij;/加上第i部件由j供應(yīng)商提供的重量l += cij;/加上第i部件由j供應(yīng)商提供的價(jià)格Search(i+1