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

一、算法实现题5-3 最小重量机器设计问题设某一机器由n个部件组成，每一种部件都可以从m个不同的供应商处购得。设wij是从供应商j处购得的部件i的重量，cij是相应的价格，给出总价格不超过d的最小重量机器设计。1、解题说明这是一个最优规划问题，采用本章回溯法来求解。解空间是一个子集树，因此通过递归函数对解空间进行深度优先搜索，只要在当前结点，只要满足限定条件和限界条件，则递归下一层，否则就尝试下一个供应商。Backtrack(1)实现对整个解空间的回溯搜索，Backtrack（i）搜索解空间中第i层子树。类Machine的数据成员记录界空间中结点信息。在算法Backtrack中，当in的时候，算法搜索至叶节点，得到一个新的可行解，与当前最优解进行比较，并更新最优值。当i=n的时候，当前扩展结点是解空间中的内部结点。该结点有m个子节点。若满足当前总费用小于最大总费用，并且当前总重量小于最小总重量，那么以深度优先的方式递归地对可行子树进行搜索，或剪去不可行子树。2、程序代码#include#includeusing namespace std;class Machine /机器类public:Machine() /构造函数cw=cc=0;minw=1000; ifstream in(input.txt); /从文件输入 innmd;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;jcij;w=new double*n+1; /创建部件重量二维数组for(i=1;i=n;i+)wi=new doublem+1;for(i=1;i=n;i+) /从文件读入重量for(int j=1;jwij;void Backtrack(int i) if(in) /已得到一个可行解if(cwminw) /更新最小重量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&cwminw) Backtrack(i+1); /考虑下一个供应商cc-=cij;cw-=wij; void Output() /输出到文件ofstream out(output.txt);coutminwendl;outminwendl;for(int k=1;k=m;k+)outbestproviderk ;coutbestproviderk ;outendl;coutn的时候，算法搜索至叶节点，得到新的排列方案。若当前总费用小于最小总费用，则更新最小总费用的值。并返回。 当i=n的时候，当前扩展结点位于排列树中，此时算法判断当前总费用是否小于最小总费用，若小于，则以深度优先的方式递归地对相应子树进行搜索。否则剪去相应子树。2、程序代码#include#includeusing namespace std;class Work /工作类public:Work() /构造函数cc=0; /当前总费用赋初值为0minc=10000; /最小费用赋初值为10000ifstream in(input.txt); /从文件读入n inn;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;jcij;coutcij ;coutn) /已得到一个可行解if(ccminc) /更新最小费用minc=cc;return;for(int j=i;j=n;j+) if(ccminc) /搜索子树swap(worki,workj);cc+=ciworki;Backtrack(i+1);cc-=ciworki;swap(workj,worki);void Output()ofstream out(output.txt);coutmincendl;outmincendl;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.Backtrack(1);wk.Output();return 0;3、运行截图1）程序所在文件夹有input.txt，运行完成后产生