最小重量機器設計問題+工作分配問題.doc

《最小重量機器設計問題+工作分配問題.doc》由會員上傳分享，免費在線閱讀，更多相關內容在教育資源-天天文庫。

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

2、結點信息。在算法Backtrack中，當i>n的時候，算法搜索至葉節(jié)點，得到一個新的可行解，與當前最優(yōu)解進行比較，并更新最優(yōu)值。當i<=n的時候，當前擴展結點是解空間中的內部結點。該結點有m個子節(jié)點。若滿足當前總費用小于最大總費用，并且當前總重量小于最小總重量，那么以深度優(yōu)先的方式遞歸地對可行子樹進行搜索，或剪去不可行子樹。2、程序代碼#include#includeusingnamespacestd;classMachine{//機器類public:Machine(){//構造函數cw=cc=0;minw=1000;if

3、streamin("input.txt");//從文件輸入in>>n>>m>>d;bestprovider=newint[m+1];//初始化最優(yōu)供應商和供應商數組provider=newint[m+1];c=newdouble*[n+1];//創(chuàng)建部件價格二維數組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)建部件重量二維數組for(i=1;i<=n;i++)..w[i]=n

4、ewdouble[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、遞歸下一層if(cc<=d&&cw

6、個數，d為總價格上屆，i為層數double**w;//部件重量數組double**c;//部件價格數組doublecw,cc,minw;//cw為當前重量，cc為當前價格，minw為最小重量int*provider;//供應商數組int*bestprovider;//最優(yōu)供應商數組};intmain(){Machinemach;mach.Backtrack(1);mach.Output();return0;}3、運行截圖1）程序所在文件夾有input.txt，運行完成后產生了output.txt2）輸入文件input.txt第一行分別是部件數量n，供應商數量m

7、，和最大費用d；緊接著輸入一個n行m列的部件價格數組和一個n行m列的部件重量數組。..3）運行程序后，打開ouput.txt，輸出結果如下：Dos界面運行如下：二、算法實現(xiàn)題5-13工作分配問題設有n件工作分配給n個人。將工作i分配給第j個人所需的費用為cij。試設計一個算法，為每一個人都分配1件不同的工作，并使總費用達到最小。設計一個算法，對于給定的工作費用，計算最佳工作分配方案，使總費用達到最小。1、解題說明工作分配問題的解空間是一個排列樹。按照回溯法搜索排列數的算法框架。相應的排列樹由work[1:n]的所有排列給出。在遞歸算法Backtrack中，當i

8、>n的時候，算法搜索至葉節(jié)點，得到新的