《算法設計》課程報告__最小重量機器設計問題

《《算法設計》課程報告__最小重量機器設計問題》由會員上傳分享，免費在線閱讀，更多相關內容在行業(yè)資料-天天文庫。

1、課程名稱：學生姓名：學生學號：《算法設計》課程報告課題名稱：算法設計課題負責人名（學號）：---同組成員名單（角色）：---指導教師：---評閱成績：評閱意見：提交報告時間：2014年6月17日-10-課程名稱：學生姓名：學生學號：最小重量機器設計問題計算機科學與技術專業(yè)學生--指導老師---[題目描述]設某一機器由n個部件組成，每一種部件都可以從m個不同的供應商處購得。高wij是從供應商j處購得的部件i的重量，cij是相應的價格。試設計一個算法，給出總價格不超過c的最小重量機器設計。編程任務：對于給定的機器部件重量和機器部件價格，

2、編程計算總價格不超過d的最小重量機器設計。數(shù)據(jù)輸入：由文件input.txt給出輸入數(shù)據(jù)。第一行有3個正整數(shù)n，m和d。接正業(yè)的2n行，每行n個數(shù)。前n行是c，后n行是w。結果輸出：將計算出的最小重量，以及每個部件的供應商輸出到文件output.txt。輸入文件示例輸出文件示例input.txtoutput.txt3344123131321222123321222-10-課程名稱：學生姓名：學生學號：[算法分析]采用回溯算法和分支定界法分別實現(xiàn)，對于回溯法，采用深度優(yōu)先搜索對子集樹進行剪枝，剪枝條件是當前的總費用不超過總費用；對于分

3、支定界法，采用按照層次遍歷對子集樹進行剪枝，并將每層的結點按照重量由小到大進行排序，將相應下標保存在二維數(shù)組s中，以便構造最優(yōu)解。兩種算法是時間復雜度都是O(m^n)，空間復雜度均為O(nm)，但由于分支定界法在已經(jīng)排好序的序列中查找，因此查找到的第一個解即為最優(yōu)解，理論上來說，時間效率會比回溯法高。[程序實現(xiàn)]回溯法代碼#include#include#include#include#include#includeusi

4、ngnamespacestd;#defineINF999999999#defineMAXSIZE100+1intcur_solution[MAXSIZE];intsolution[MAXSIZE];intw[MAXSIZE][MAXSIZE];//weightintc[MAXSIZE][MAXSIZE];//costintminWeight;intcur_minWeight;voidBacktrack(intt,intn,intm,intd){-10-課程名稱：學生姓名：學生學號：if(t>n){if(cur_minWeight

5、inWeight){//保存最優(yōu)解和最優(yōu)值minWeight=cur_minWeight;for(intr=1;r<=n;++r){solution[r]=cur_solution[r];}}}else{for(inti=1;i<=m;++i){d-=c[t][i];cur_solution[t]=i;cur_minWeight+=w[t][i];if(d>=0){Backtrack(t+1,n,m,d);}cur_minWeight-=w[t][i];//if(Constraint(t)&&Bound(t))Backtrack(t

6、+1,n,m,d);d+=c[t][i];}}return;}intmain(){intn,m,d;cout<<"Pleaseinputtheinputfilepath:"<>strPath;ofstreamfout(strPath);if(fin.good

7、()&&fout.good()){minWeight=INF;cur_minWeight=0;fin>>n>>m>>d;intj,k;for(j=1;j<=n;++j){for(k=1;k<=m;++k){fin>>c[j][k];}}for(j=1;j<=n;++j){for(k=1;k<=m;++k){fin>>w[j][k];}}Backtrack(1,n,m,d);fout<

8、.close();fin.close();}else{cout<<"Openfileerror!"<