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

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

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

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

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

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

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

7、果肯定不包含，則跳過對以該結(jié)點為根的子樹的系統(tǒng)搜索，逐層向其祖先結(jié)點回溯。否則，進入該子樹，繼續(xù)按深度優(yōu)先的策略進行搜索。回溯法在用來求問題的所有解時，要回溯到根，且根結(jié)點的所有子樹都已被搜索遍才結(jié)束。而回溯法在用來求問題的任一解時，只要搜索到問題的一個解就可以結(jié)束。這種以深度優(yōu)先的方式系統(tǒng)地搜索問題的解的算法稱為回溯法，它適用于解一些組合數(shù)較大的問題。四、問題分析與設(shè)計4.1k乘積問題1.分析最優(yōu)解的結(jié)構(gòu)為了方便起見，設(shè)I(s,t)是I的由s位開始的t位數(shù)字組成的十進制數(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時，MaxIn1 = I(0,n);當(dāng)k1時，可利用最優(yōu)子結(jié)構(gòu)性質(zhì)計算MaxInk, 若計算MaxInk的第k段的起始位置為第w位，1wj，則有MaxInk = MaxIwk-1×I(w,n-w)。由于在計算時并不知道第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)值，同時還確定了計算最優(yōu)的斷開位置w，也就時說，對于這個w有 MaxInk = MaxIwk-1×I(w,n-w)若將對應(yīng)于MaxInk的斷開位置w記為demarcationnk后，可遞歸地由 demarcationnk構(gòu)造相應(yīng)的最優(yōu)解。4.2最小重量機器設(shè)計問題1.用遞歸函數(shù)backtrack(i)來實現(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，則算法搜索到一個葉結(jié)點，用weight對最優(yōu)解進行記錄，返回到i-1層繼續(xù)執(zhí)行； 用for循環(huán)對部件i從m個不同的供應(yīng)商購得的情況進行選擇(1jm）。 2.主函數(shù)調(diào)用一次backtrack(1)即可完成整個回溯搜索過程，最終得到的weight即為所求最小總重量，p為該機器最小重量的價格。 五、算法實現(xiàn)5.1k乘積問題#include<stdio.h>#include<string.h>#include<stdlib.h>#define MAXN 51#define MAXK 10/mij表示1i十進制位分成j段所

12、得的最大乘積long mMAXKMAXN=0,0 ;/wij表示ij十進制位所組成的十進制數(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個數(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最小重量機器問題/*頭文件 最小重量機器設(shè)計問題.h*/#ifndef KNAP_H#define KNAP_

17、H#include <iostream>#include <fstream>using namespace std;class Machine/機器類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個部件開始遞歸搜索void Print();/輸出結(jié)果private:int n;/部件個數(shù)int m;/供應(yīng)商個數(shù)int d;/價格上限int *w;/部件重量

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

19、> n >> m >> d;/初始化部件個數(shù)n，供應(yīng)商數(shù)m，價格限制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;/初始化部件價格fin.close();min = IN

20、T_MAX;/初始化最小重量plan = new intn+1;for(int i = 1; i <= n; i+)plani = 0;/初始化選購計劃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);/第一個零件開始搜索，初始重量和價格是0Print();/輸出函數(shù)void Machine:Search(int i, int s, int l, int *e)if(i = n+1)/選購?fù)戤卛f(s < min && l <= d)/找到一個更優(yōu)解min = s;/更新重量最小值for(int i = 1; i <= n; i+)plani = ei;/更新選購計劃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)商提供的價格Search(i+1