最小重量機器設(shè)計問題工作分配問題

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

1、一、算法實現(xiàn)題5-3最小重量機器設(shè)計問題設(shè)某一機器由n個部件組成,每一種部件都可以從m個不同的供應(yīng)商處購得。設(shè)w[i][j]是從供應(yīng)商j處購得的部件i的重量，di][j]是相應(yīng)的價格，給出總價格不超過d的最小重量機器設(shè)計。1、解題說明這是一個最優(yōu)規(guī)劃問題，采用木章回溯法來求解。解空間是一個子集樹，因此通過遞歸函數(shù)對解空間進行深度優(yōu)先搜索，只要在當(dāng)前結(jié)點，只要滿足限定條件和限界條件，則遞歸下一層，否則就嘗試下一個供應(yīng)商。Backtrack(1)實現(xiàn)對整個解空間的回溯搜索，Backtrack(i)搜索解空間中第i層子樹。類

2、Machine的數(shù)據(jù)成員記錄界空間中結(jié)點信息。在算法Backtrack中，當(dāng)i〉n的時候，算法搜索至葉節(jié)點，得到一個新的可行解，與當(dāng)前最優(yōu)解進行比較，并更新最優(yōu)值。當(dāng)i〈=n的時候，當(dāng)前擴展結(jié)點是解空間屮的內(nèi)部結(jié)點。該結(jié)點有m個子節(jié)點。若滿足當(dāng)前總費用小于最大總費用，并且當(dāng)前總重量小于最小總重量，那么以深度優(yōu)先的方式遞歸地對可行子樹進行搜索，或剪去不可行子樹。2、程序代碼#include#includeusingnamespacestd;classMachine{//機器類publ

3、ic:MachineO{//構(gòu)造函數(shù)cw=cc=0;minw=1000;ifstreamin("i叩ut.txt");//從文件輸入in?n>>m?d;bestprovider=newint[m+l];//初始化最優(yōu)供應(yīng)商和供應(yīng)商數(shù)組provider=newint[ni+1];c=newdouble[n+l];//創(chuàng)建部件價格二維數(shù)組for(i=l;i〈=n;i++)c[i]=newdouble[m+l];for(i=l;i<=n;i++)//從文件瀆入價格for(intj=l;j<=m;j++)in〉〉c[i][j]

4、;//創(chuàng)逑部件東量二維數(shù)組w=newd()uble[n+l];for(i=l;i〈=n;i++)[i]=ncwdouble[m+l];for(i=l;i<=n;i++)//從文件讀入重量for(intj=l;j<=m;j++)in?w[i][j];voidBacktrack(inti){if(i〉n){//己得到一個可行解if(cw〈minw){//更新最小重量mimv-cw;for(intj=l;j<=m;j++)bestprovider[j]二provider[j];}return;for(intj=l;j<=m;

5、j++){provider[i]二j;//考慮第j個供應(yīng)商cc+=c[i][j];cw+=w[i][j];//滿足限定條件并且滿足限界條件，則遞歸下一層if(cc<=d&&cw

6、';cout<

7、ach.Output();return0;3、運行截圖1）程序所在文件夾有input,txt,運行完成后產(chǎn)生了output,txtDebugtjinputtxtoutput.txt最小重墾機器設(shè)計冋監(jiān)xpp最小重墾機器設(shè)計間g.dsp_最小雪墾機囂設(shè)計冋E.ncb_最小重墾機器設(shè)計間琵.opt_最小雪墾機囂設(shè)計冋E.plg2）輸入文件input,txt第一行分別是部件數(shù)量n，供應(yīng)商數(shù)量m，和最大費用d;緊接著輸入一個n行m列的部件價格數(shù)組和一個n行m列的部件重量數(shù)組。邏input.txt?享本文件(F)顚(E)格式(0

8、3341233212221233212223)運行程序后，打開ouput.txt,輸出結(jié)果如下:output.txt-記事本文件(F)騎E)格式(O)查看(V)4131Dos界面運行如下:<■懺:我的匚++職算法冊與分析5-31131Pressanykeytocontinue二、算法實現(xiàn)題5-13工作分配問題設(shè)有n件工作分配給