最小重量机器设计问题+工作分配问题

1、一、算法实现题5-3 最小重量机器设计问题设某一机器由n个部件组成，每一种部件都可以从m个不同的供应商处购得。设wij是从供应商j处购得的部件i的重量，cij是相应的价格，给出总价格不超过d的最小重量机器设计。 1、解题说明这是一个最优规划问题，采用本章回溯法来求解。解空间是一个子集树，因此通过递归函数对解空间进行深度优先搜索，只要在当前结点，只要满足限定条件和限界条件，那么递归下一层，否那么就尝试下一个供应商。Backtrack(1)实现对整个解空间的回溯搜索，Backtracki搜索解空间中第i层子树。类Machine的数据成员记录界空间中结点信息。在算法Backtrack中，当

2、i>n的时候，算法搜索至叶节点，得到一个新的可行解，与当前最优解进行比较，并更新最优值。当i<=n的时候，当前扩展结点是解空间中的内部结点。该结点有m个子节点。假设满足当前总费用小于最大总费用，并且当前总重量小于最小总重量，那么以深度优先的方式递归地对可行子树进行搜索，或剪去不可行子树。2、程序代码#include<iostream>#include<fstream>using namespace std;class Machine /机器类public:Machine() /构造函数cw=cc=0;minw=1000; ifstream in("

3、input.txt"); /从文件输入 in>>n>>m>>d;bestprovider=new intm+1; /初始化最优供应商和供应商数组provider=new intm+1;c=new double*n+1; /创立部件价格二维数组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; /创立部件重量二维数组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个供应商cc+=cij;cw+=wij; /满足限定条件并且满足限界条件，那么递归下一层if(cc<=d&

5、amp;&cw<minw) Backtrack(i+1); /考虑下一个供应商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为部件个数，m为供应商个数，d为总价格上届，i为层数double *w; /部件重量数组double *c; /部件价格数组double cw,cc,minw; /cw为当前重量，cc为当前价格，minw为最小重量int *provider; /供应商数组int *bestprovider; /最优供应商数组;int main()Machine mach;mach.Backtrack(1);mach.Output();return 0;3、运行截图 1程序所在文件夹有input.txt，运行完成后产生了out

7、put.txt 2输入文件input.txt 第一行分别是部件数量n，供应商数量m，和最大费用d； 紧接着输入一个n行m列的部件价格数组和一个n行m列的部件重量数组。 3运行程序后，翻开ouput.txt，输出结果如下： Dos界面运行如下：二、算法实现题5-13 工作分配问题设有n件工作分配给n个人。将工作i分配给第j个人所需的费用为cij 。试设计一个算法，为每一个人都分配1 件不同的工作，并使总费用到达最小。设计一个算法，对于给定的工作费用，计算最正确工作分配方案，使总费用到达最小。1、解题说明 工作分配问题的解空间是一个排列树。按照回溯法搜索排列数的算法框架。相应的排列树由work1:

8、n的所有排列给出。 在递归算法Backtrack中，当i>n的时候，算法搜索至叶节点，得到新的排列方案。假设当前总费用小于最小总费用，那么更新最小总费用的值。并返回。 当i<=n的时候，当前扩展结点位于排列树中，此时算法判断当前总费用是否小于最小总费用，假设小于，那么以深度优先的方式递归地对相应子树进行搜索。否那么剪去相应子树。2、程序代码#include<iostream>#include<fstream>using namespace std;class Work /工作类public:Work() /构造函数cc=0; /当前总费用赋初值为0minc=

9、10000; /最小费用赋初值为10000ifstream in("input.txt"); /从文件读入n in>>n;work=new intn+1; /初始化工作数组for(i=1;i<=n;i+)worki=i;c=new int*n+1; /创立费用二维数组for(i=1;i<=n;i+)ci=new intn+1;for(i=1;i<=n;i+) /从文件读入二维数组 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) /更新最小费用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