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

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

2、i>n的時(shí)候，算法搜索至葉節(jié)點(diǎn)，得到一個(gè)新的可行解，與當(dāng)前最優(yōu)解進(jìn)行比較，并更新最優(yōu)值。當(dāng)i<=n的時(shí)候，當(dāng)前擴(kuò)展結(jié)點(diǎn)是解空間中的內(nèi)部結(jié)點(diǎn)。該結(jié)點(diǎn)有m個(gè)子節(jié)點(diǎn)。假設(shè)滿足當(dāng)前總費(fèi)用小于最大總費(fèi)用，并且當(dāng)前總重量小于最小總重量，那么以深度優(yōu)先的方式遞歸地對(duì)可行子樹(shù)進(jìn)行搜索，或剪去不可行子樹(shù)。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)立部件價(jià)格二維數(shù)組for(i=1;i<=n;i+)ci=new doublem+1;for(i=1;i<=n;i+) /從文件讀入價(jià)格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) /已得到一個(gè)可行解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個(gè)供應(yīng)商cc+=cij;cw+=wij; /滿足限定條件并且滿足限界條件，那么遞歸下一層if(cc<=d&

5、amp;&cw<minw) Backtrack(i+1); /考慮下一個(gè)供應(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為部件個(gè)數(shù)，m為供應(yīng)商個(gè)數(shù)，d為總價(jià)格上屆，i為層數(shù)double *w; /部件重量數(shù)組double *c; /部件價(jià)格數(shù)組double cw,cc,minw; /cw為當(dāng)前重量，cc為當(dāng)前價(jià)格，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； 緊接著輸入一個(gè)n行m列的部件價(jià)格數(shù)組和一個(gè)n行m列的部件重量數(shù)組。 3運(yùn)行程序后，翻開(kāi)ouput.txt，輸出結(jié)果如下： Dos界面運(yùn)行如下：二、算法實(shí)現(xiàn)題5-13 工作分配問(wèn)題設(shè)有n件工作分配給n個(gè)人。將工作i分配給第j個(gè)人所需的費(fèi)用為cij 。試設(shè)計(jì)一個(gè)算法，為每一個(gè)人都分配1 件不同的工作，并使總費(fèi)用到達(dá)最小。設(shè)計(jì)一個(gè)算法，對(duì)于給定的工作費(fèi)用，計(jì)算最正確工作分配方案，使總費(fèi)用到達(dá)最小。1、解題說(shuō)明 工作分配問(wèn)題的解空間是一個(gè)排列樹(shù)。按照回溯法搜索排列數(shù)的算法框架。相應(yīng)的排列樹(shù)由work1:

8、n的所有排列給出。 在遞歸算法Backtrack中，當(dāng)i>n的時(shí)候，算法搜索至葉節(jié)點(diǎn)，得到新的排列方案。假設(shè)當(dāng)前總費(fèi)用小于最小總費(fèi)用，那么更新最小總費(fèi)用的值。并返回。 當(dāng)i<=n的時(shí)候，當(dāng)前擴(kuò)展結(jié)點(diǎn)位于排列樹(shù)中，此時(shí)算法判斷當(dāng)前總費(fèi)用是否小于最小總費(fèi)用，假設(shè)小于，那么以深度優(yōu)先的方式遞歸地對(duì)相應(yīng)子樹(shù)進(jìn)行搜索。否那么剪去相應(yīng)子樹(shù)。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) /已得到一個(gè)可行解if(cc<minc) /更新最小費(fèi)用minc=cc;return;for(int j=i;j<=n;j+) if(cc<minc) /搜索子樹(shù)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