實驗報告最小重量機(jī)器設(shè)計問題

《實驗報告最小重量機(jī)器設(shè)計問題》由會員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在學(xué)術(shù)論文-天天文庫。

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

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

3、出4131將計算出的最小重兒:，以及每個部什的供應(yīng)商分成兩行輸出。無解請輸出“NoSolution!”。示例輸入334123321222123321222三、實驗步驟1.理解冋溯算法思想和算法示例；2.上機(jī)輸入和調(diào)試算法示例程序；3.理解實驗題的問題要求；4.上機(jī)輸入和調(diào)試&己所編的實驗題程序；5.驗證并分析實驗題的實驗結(jié)果；6.整理出實驗報告。代碼如下：#includeusingnamespacestd;constintlen=30;constintmaxWeight=4000;intn，

4、m，cost;intw[len][len];//重量intc[len][len];//價錢intvisit

5、len

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

7、fj]<=cost&&weight+w[i][j]

8、

9、j

10、;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

11、

12、i

13、

14、j

15、;elsecin?w[i-n][j];}}findMinWeight(O,O,O);if(minWeight==maxWeight)cout<<"-1"?endl;elsecout?minWeight?endl;for(i=0;i

16、成績評定:指導(dǎo)教師簽名：