《算法設(shè)計(jì)》課程報(bào)告__最小重量機(jī)器設(shè)計(jì)問(wèn)題

《《算法設(shè)計(jì)》課程報(bào)告__最小重量機(jī)器設(shè)計(jì)問(wèn)題》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫(kù)。

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

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

3、支定界法，采用按照層次遍歷對(duì)子集樹(shù)進(jìn)行剪枝，并將每層的結(jié)點(diǎn)按照重量由小到大進(jìn)行排序，將相應(yīng)下標(biāo)保存在二維數(shù)組s中，以便構(gòu)造最優(yōu)解。兩種算法是時(shí)間復(fù)雜度都是O(m^n)，空間復(fù)雜度均為O(nm)，但由于分支定界法在已經(jīng)排好序的序列中查找，因此查找到的第一個(gè)解即為最優(yōu)解，理論上來(lái)說(shuō)，時(shí)間效率會(huì)比回溯法高。[程序?qū)崿F(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-課程名稱：學(xué)生姓名：學(xué)生學(xué)號(hào)：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!"<