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

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

2、i>n的時候，算法搜索至葉節(jié)點(diǎn)，得到一個新的可行解，與當(dāng)前最優(yōu)解進(jìn)行比較，并更新最優(yōu)值。當(dāng)i<=n的時候，當(dāng)前擴(kuò)展結(jié)點(diǎn)是解空間中的內(nèi)部結(jié)點(diǎn)。該結(jié)點(diǎn)有m個子節(jié)點(diǎn)。假設(shè)滿足當(dāng)前總費(fèi)用小于最大總費(fèi)用，并且當(dāng)前總重量小于最小總重量，那么以深度優(yōu)先的方式遞歸地對可行子樹進(jìn)行搜索，或剪去不可行子樹。2、程序代碼#include<iostream>#include<fstream>using namespace std;class Machine /機(jī)器類public:Machine() /構(gòu)造函數(shù)cw=cc=0;minw=1000; ifstream in("

3、input.txt"); /從文件輸入 in>>n>>m>>d;bestprovider=new intm+1; /初始化最優(yōu)供應(yīng)商和供應(yīng)商數(shù)組provider=new intm+1;c=new double*n+1; /創(chuàng)立部件價格二維數(shù)組for(i=1;i<=n;i+)ci=new doublem+1;for(i=1;i<=n;i+) /從文件讀入價格for(int j=1;j<=m;j+)in>>cij;w=new double*n+1; /創(chuàng)立部件重量二維數(shù)組for(i=1;i<=n;i+)wi=new

4、doublem+1;for(i=1;i<=n;i+) /從文件讀入重量for(int j=1;j<=m;j+)in>>wij;void Backtrack(int i) if(i>n) /已得到一個可行解if(cw<minw) /更新最小重量minw=cw;for(int j=1;j<=m;j+) bestproviderj=providerj;return; for(int j=1;j<=m;j+) provideri=j;/考慮第j個供應(yīng)商cc+=cij;cw+=wij; /滿足限定條件并且滿足限界條件，那么遞歸下一層if(cc<=d&

5、amp;&cw<minw) Backtrack(i+1); /考慮下一個供應(yīng)商cc-=cij;cw-=wij; void Output() /輸出到文件ofstream out("output.txt");cout<<minw<<endl;out<<minw<<endl;for(int k=1;k<=m;k+)out<<bestproviderk<<' 'cout<<bestproviderk<<' 'out<<en

6、dl;cout<<endl;private:int n,m,d,i; /n為部件個數(shù)，m為供應(yīng)商個數(shù)，d為總價格上屆，i為層數(shù)double *w; /部件重量數(shù)組double *c; /部件價格數(shù)組double cw,cc,minw; /cw為當(dāng)前重量，cc為當(dāng)前價格，minw為最小重量int *provider; /供應(yīng)商數(shù)組int *bestprovider; /最優(yōu)供應(yīng)商數(shù)組;int main()Machine mach;mach.Backtrack(1);mach.Output();return 0;3、運(yùn)行截圖 1程序所在文件夾有input.txt，運(yùn)行完成后產(chǎn)生了out

7、put.txt 2輸入文件input.txt 第一行分別是部件數(shù)量n，供應(yīng)商數(shù)量m，和最大費(fèi)用d； 緊接著輸入一個n行m列的部件價格數(shù)組和一個n行m列的部件重量數(shù)組。 3運(yùn)行程序后，翻開ouput.txt，輸出結(jié)果如下： Dos界面運(yùn)行如下：二、算法實(shí)現(xiàn)題5-13 工作分配問題設(shè)有n件工作分配給n個人。將工作i分配給第j個人所需的費(fèi)用為cij 。試設(shè)計一個算法，為每一個人都分配1 件不同的工作，并使總費(fèi)用到達(dá)最小。設(shè)計一個算法，對于給定的工作費(fèi)用，計算最正確工作分配方案，使總費(fèi)用到達(dá)最小。1、解題說明 工作分配問題的解空間是一個排列樹。按照回溯法搜索排列數(shù)的算法框架。相應(yīng)的排列樹由work1:

8、n的所有排列給出。 在遞歸算法Backtrack中，當(dāng)i>n的時候，算法搜索至葉節(jié)點(diǎn)，得到新的排列方案。假設(shè)當(dāng)前總費(fèi)用小于最小總費(fèi)用，那么更新最小總費(fèi)用的值。并返回。 當(dāng)i<=n的時候，當(dāng)前擴(kuò)展結(jié)點(diǎn)位于排列樹中，此時算法判斷當(dāng)前總費(fèi)用是否小于最小總費(fèi)用，假設(shè)小于，那么以深度優(yōu)先的方式遞歸地對相應(yīng)子樹進(jìn)行搜索。否那么剪去相應(yīng)子樹。2、程序代碼#include<iostream>#include<fstream>using namespace std;class Work /工作類public:Work() /構(gòu)造函數(shù)cc=0; /當(dāng)前總費(fèi)用賦初值為0minc=

9、10000; /最小費(fèi)用賦初值為10000ifstream in("input.txt"); /從文件讀入n in>>n;work=new intn+1; /初始化工作數(shù)組for(i=1;i<=n;i+)worki=i;c=new int*n+1; /創(chuàng)立費(fèi)用二維數(shù)組for(i=1;i<=n;i+)ci=new intn+1;for(i=1;i<=n;i+) /從文件讀入二維數(shù)組 for(int j=1;j<=n;j+)in>>cij;cout<<cij<<" "cout<&l

10、t;endl;void Backtrack(int i) if(i>n) /已得到一個可行解if(cc<minc) /更新最小費(fèi)用minc=cc;return;for(int j=i;j<=n;j+) if(cc<minc) /搜索子樹swap(worki,workj);cc+=ciworki;Backtrack(i+1);cc-=ciworki;swap(workj,worki);void Output()ofstream out("output.txt");cout<<minc<<endl;out<<minc<<endl;public:int n,i,j;int *c;int *work;int cc,minc;void swap(int &a,int &b)int temp=a;a=b;b=temp;int main()Work wk;wk.Backtrac