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

《最小重量機器設(shè)計問題+工作分配問題》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在應(yīng)用文檔-天天文庫。

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

2、據(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{//機器類public:Machine(){//構(gòu)造函數(shù)c

3、w=cc=0;minw=1000;ifstreamin("input.txt");//從文件輸入in>>n>>m>>d;bestprovider=newint[m+1];//初始化最優(yōu)供應(yīng)商和供應(yīng)商數(shù)組provider=newint[m+1];c=newdouble*[n+1];//創(chuàng)建部件價格二維數(shù)組for(i=1;i<=n;i++)c[i]=newdouble[m+1];for(i=1;i<=n;i++)//從文件讀入價格for(intj=1;j<=m;j++)in>>c[i][j];w=newdouble*[n+1];//創(chuàng)建部件重量

4、二維數(shù)組for(i=1;i<=n;i++)w[i]=newdouble[m+1];for(i=1;i<=n;i++)//從文件讀入重量for(intj=1;j<=m;j++)in>>w[i][j];}voidBacktrack(inti){if(i>n){//已得到一個可行解if(cw

5、[i][j];cw+=w[i][j];//滿足限定條件并且滿足限界條件，則遞歸下一層if(cc<=d&&cw

6、cout<

7、txt，運行完成后產(chǎn)生了output.txt2）輸入文件input.txt第一行分別是部件數(shù)量n，供應(yīng)商數(shù)量m，和最大費用d；緊接著輸入一個n行m列的部件價格數(shù)組和一個n行m列的部件重量數(shù)組。3）運行程序后，打開ouput.txt，輸出結(jié)果如下：Dos界面運行如下：二、算法實現(xiàn)題5-13工作分配問題設(shè)有n件工作分配給n個人。將工作i分配給第j個人所需的費用為cij。試設(shè)計一個算法，為每一個人都分配1件不同的工作，并使總費用達到最小。設(shè)計一個算法，對于給定的工作費用，計算最佳工作分配方案，使總費用達到最小。1、解題說明工作分配問題的解空間是一

8、個排列樹。按照回溯法搜索排列數(shù)的算法框架。相應(yīng)的排列樹由work[1:n]的所有排列給出。在遞歸算法Backtrack中，當(dāng)i>n的時候，算法搜索至葉節(jié)點，得到新的排列方案。若當(dāng)