最小重量機(jī)器設(shè)計(jì)問題

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

1、最小重量機(jī)器設(shè)計(jì)問題1.問題描述設(shè)某一機(jī)器由n個(gè)部件組成，每一個(gè)部件都可以從m個(gè)不同的供應(yīng)商處購(gòu)得。設(shè)wij是從供應(yīng)商j處購(gòu)得的部件i的重量，cij是相應(yīng)的價(jià)格。試設(shè)計(jì)一個(gè)算法，給出總價(jià)格不超過c的最小重量機(jī)器設(shè)計(jì)。算法設(shè)計(jì)：對(duì)于給定的機(jī)器部件重量和機(jī)器部件價(jià)格，計(jì)算總價(jià)格不超過d的最小重量機(jī)器設(shè)計(jì)。2.算法流程分析設(shè)開始時(shí)bestx=[-1,-1,…,-1]則相應(yīng)的排列樹由x[0:n-1]的所有排列構(gòu)成。找最小重量機(jī)器設(shè)計(jì)的回溯算法Backtrack是類machine的公有成員。私有數(shù)據(jù)成員整型數(shù)組Savex保存搜索過的路徑，到達(dá)葉節(jié)點(diǎn)后將數(shù)據(jù)賦值給數(shù)組bestx。成員bestw記

2、錄當(dāng)前最小重量，cc表示當(dāng)前花費(fèi)，cw表示當(dāng)前的重量。在遞歸函數(shù)Backtrack中，在保證總花費(fèi)不超過c的情況下：當(dāng)i=n時(shí)，當(dāng)前擴(kuò)展結(jié)點(diǎn)是排列樹的葉節(jié)點(diǎn)。此時(shí)搜索到一個(gè)解，判斷此時(shí)的最小重量是否小于當(dāng)前最小重量，若小于則更新bestw，并得到搜索路徑bestx。當(dāng)i

3、曉東編著，計(jì)算機(jī)算法設(shè)計(jì)與分析（第4版）。北京：電子工業(yè)出版社，2012.26.附錄（1）可執(zhí)行代碼如下：#includeusingnamespacestd;#defineN50classMinWmechine{intn;//部件個(gè)數(shù)intm;//供應(yīng)商個(gè)數(shù)intCOST;//題目中的Cintcw;//當(dāng)前的重量intcc;//當(dāng)前花費(fèi)intbestw;//當(dāng)前最小重量intbestx[N];intsavex[N];intw[N][N];intc[N][N];public:MinWmechine();voidmachine_plan(inti);voidprino

4、ut();};MinWmechine::MinWmechine(){cw=0;//當(dāng)前的重量cc=0;//當(dāng)前花費(fèi)bestw=-1;//當(dāng)前最小重量bestx[N];savex[N];cout<<"請(qǐng)輸入部件個(gè)數(shù)：";cin>>n;cout<<"請(qǐng)輸入供應(yīng)商個(gè)數(shù)：";cin>>m;cout<<"請(qǐng)輸入總價(jià)格不超過：";cin>>COST;for(intj=0;j>w[i][j];cout<<"請(qǐng)輸入第"<

5、>c[i][j];if(w[i][j]<0

6、

7、c[i][j]<0){cout<<"重量或價(jià)錢不能為負(fù)數(shù)！";i=i-1;}}}}voidMinWmechine::machine_plan(inti){if(i>=n){if(cw

8、

9、bestw==-1){bestw=cw;for(intj=0;j

10、][j];bestx[i]=j;machine_plan(i+1);bestx[i]=-1;cc-=c[i][j];cw-=w[i][j];}}}voidMinWmechine::prinout(){inti,j,ccc=0;for(j=0;j

11、endl;for(intk=0;k