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

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

一、算法实现题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++)