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

最小重量机器设计问题+工作分配问题一、算法实现题5-3最小重量机器设计问题 设某一机器由n个部件组成，每一种部件都可以从m个不同的供应商处购得。设w[i][j]是从供应商j处购得的部件i的重量，c[i][j]是相应的价格，给出总价格不超过d的最小重量机器设计。

1、解题说明这是一个最优规划问题，采用本章回溯法来求解。解空间是一个子集树，因此通过递归函数对解空间进行深度优先搜索，只要在当前结点，只要满足限定条件和限界条件，则递归下一层，否则就尝试下一个供应商。Backtrack(1)实现对整个解空间的回溯搜索，Backtrack（i）搜索解空间中第i层子树。类Machine的数据成员记录界空间中结点信息。在算法Backtrack中，当i>n的时候，算法搜索至叶节点，得到一个新的可行解，与当前最优解进行比较，并更新最优值。当i<=n的时候，当前扩展结点是解空间中的内部结点。该结点有m个子节点。若满足当前总费用小于最大总费用，并且当前总重量小于最小总重量，那么以深度优先的方式递归地对可行子树进行搜索，或剪去不可行子树。2、程序代码#include<iostream>#include<fstream>usingnamespacestd;classMachine{//机器类public: Machine(){//构造函数 cw=cc=0; minw=1000; ifstreamin("input.txt");//从文件输入in>>n>>m>>d; bestprovider=newint[m+1];//初始化最优供应商和供应商数组 provider=newint[m+1];c=newdouble*[n+1];//创建部件价格二维数组 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];//创建部件重量二维数组 for(i=1;i<=n;i++) w[i]=newdouble[m+1]; for(i=1;i<=n;i++)//从文件读入重量3、运行截图1）程序所在文件夹有input.txt，运行完成后产生了output.txt2）输入文件input.txt第一行分别是部件数量n，供应商数量m，和最大费用d；紧接着输入一个n行m列的部件价格数组和一个n行m列的部件重量数组。3）运行程序后，打开ouput.txt，输出结果如下：Dos界面运行如下：二、算法实现题5-13工作分配问题 设有n件工作分配给n个人。将工作i分配给第j个人所需的费用为cij。试设计一个算法，为每一个人都分配1件不同的工作，并使总费用达到最小。设计一个算法，对于给定的工作费用，计算最佳工作分配方案，使总费用达到最小。1、解题说明工作分配问题的解空间是一个排列树。按照回溯法搜索排列数的算法框架。相应的排列树由work[1:n]的所有排列给出。在递归算法Backtrack中，当i>n的时候，算法搜索至叶节点，得到新的排列方案。若当前总费用小于最小总费用，则更新最小总费用的值。并返回。当i<=n的时候，当前扩展结点位于排列树中，此时算法判断当前总费用是否小于最小总费用，若小于，则以深度优先的方式递归地对相应子树进行搜索。否则剪去相应子树。2、程序代码#include<iostream>#include<fstream>usingnamespacestd;classWork{//工作类public: Work(){//构造函数 cc=0;//当前总费用赋初值为0 minc=10000;//最小费用赋初值为10000 ifstreamin("input.txt");//从文件读入nin>>n; work=newint[n+1];//初始化工作数组 for(i=1;i<=n;i++) { work[i]=i; } c=newint*[n+1];//创建费用二维数组 for(i=1;i<=n;i++) c[i]=newint[n+1]; for(i=1;i<=n;i++){//从文件读入二维数组 for(intj=1;j<=n;j++) { in>>c[i][j]; cout<<c[i][j]<<""; } cout<<endl; } } voidBacktrack(inti){ if(i>n){//已得到一个可行解 if(cc<minc)//更新最小费用 minc=cc; return; } for(intj=i;j<=n;j++) { if(cc<minc){//搜索子树 swap(work[i],work[j]); cc+=c[i][work[i]]; Backtrack(i+1); cc-=c[i][work[i]]; swap(work[j],work[i]); } } } voidOutput(){ ofstreamout("output.txt"); cout<<minc<<endl; out<<minc<<endl; }public: intn,i,j; int**c; int*work; intcc,minc; voidswap(int&a,int&b){ inttemp=a; a=b; b=temp; }};intmain(){ Workwk; wk.Backtrack(1); wk.Output(); return0;}3、运行截图1）程序所在文件夹有input.txt，运行完成后产生了