實(shí)驗(yàn)報(bào)告 最小重量機(jī)器設(shè)計(jì)問題.doc

《實(shí)驗(yàn)報(bào)告 最小重量機(jī)器設(shè)計(jì)問題.doc》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在應(yīng)用文檔-天天文庫。

1、實(shí)驗(yàn)報(bào)告課程名稱：算法設(shè)計(jì)與分析實(shí)驗(yàn)項(xiàng)目：最小重量機(jī)器設(shè)計(jì)問題實(shí)驗(yàn)類型：綜合性□設(shè)計(jì)性□驗(yàn)證性t專業(yè)班別：姓名：學(xué)號(hào)：實(shí)驗(yàn)課室：第計(jì)算機(jī)實(shí)驗(yàn)室指導(dǎo)教師：實(shí)驗(yàn)日期：2013-12-12一、實(shí)驗(yàn)項(xiàng)目訓(xùn)練方案小組合作：是□否R小組成員：實(shí)驗(yàn)?zāi)康模?.通過回溯法的示例程序理解回溯法的基本思想；2.運(yùn)用回溯法解決實(shí)際問題進(jìn)一步加深對(duì)回溯法的理解和運(yùn)用。實(shí)驗(yàn)場地及儀器、設(shè)備和材料操作系統(tǒng)：winXP、Win7、ubuntu開發(fā)環(huán)境：VC++6.0、VisualStudio2010實(shí)驗(yàn)訓(xùn)練內(nèi)容（包括實(shí)驗(yàn)原理和操作步驟）：一、實(shí)驗(yàn)內(nèi)容：1.練習(xí)使用

2、回溯法求解“最小重量機(jī)器設(shè)計(jì)”問題。二、實(shí)驗(yàn)題題目描述設(shè)某一機(jī)器由n個(gè)部件組成，每一種部件都可以從m個(gè)不同的供應(yīng)商處購得。設(shè)wij是從供應(yīng)商j處購得的部件i的重量，cij是相應(yīng)的價(jià)格。設(shè)計(jì)一個(gè)優(yōu)先隊(duì)列式分支限界法，給出總價(jià)格不超過d的最小重量機(jī)器設(shè)計(jì)。對(duì)于給定的機(jī)器部件重量和機(jī)器部件價(jià)格，設(shè)計(jì)一個(gè)優(yōu)先隊(duì)列式分支限界法，計(jì)算總價(jià)格不超過d的最小重量機(jī)器設(shè)計(jì)。輸入輸入數(shù)據(jù)的第1行有3個(gè)正整數(shù)n，m和d（n，m<20，d<100）。接下來的2n行，每行n個(gè)數(shù)。前n行是c，后n行是w。輸出將計(jì)算出的最小重量，以及每個(gè)部件的供應(yīng)商分成兩行輸出

3、。無解請(qǐng)輸出“NoSolution!”。示例輸入334123321222123321222示例輸出4131三、實(shí)驗(yàn)步驟1．理解回溯算法思想和算法示例；2．上機(jī)輸入和調(diào)試算法示例程序；3．理解實(shí)驗(yàn)題的問題要求；4．上機(jī)輸入和調(diào)試自己所編的實(shí)驗(yàn)題程序；5．驗(yàn)證并分析實(shí)驗(yàn)題的實(shí)驗(yàn)結(jié)果；6．整理出實(shí)驗(yàn)報(bào)告。代碼如下：#includeusingnamespacestd;constintlen=30;constintmaxWeight=4000;intn,m,cost;intw[len][len];//重量intc[len]

4、[len];//價(jià)錢intvisit[len];intpath[len];intminWeight=maxWeight;voidfindMinWeight(intcurrent,intweight,inti)//當(dāng)前策略的價(jià)錢和最小重量{if(i>=n){minWeight=weight;for(intj=0;j

5、=c[i][j];weight+=w[i][j];visit[i]=j+1;findMinWeight(current,weight,i+1);current-=c[i][j];weight-=w[i][j];}}}intmain(){while(cin>>n>>m>>cost){minWeight=maxWeight;inti,j;for(i=0;i<2*n;i++){for(j=0;j>c[i][j];elsecin>>w[i-n][j];}}findMinWeight(0,0,0);if(

6、minWeight==maxWeight)cout<<"-1"<