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

《最小重量机器设计问题工作分配问题》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

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

2、Machine的数据成员记录界空间中结点信息。在算法Backtrack中，当i〉n的时候，算法搜索至叶节点，得到一个新的可行解，与当前最优解进行比较，并更新最优值。当i〈=n的时候，当前扩展结点是解空间屮的内部结点。该结点有m个子节点。若满足当前总费用小于最大总费用，并且当前总重量小于最小总重量，那么以深度优先的方式递归地对可行子树进行搜索，或剪去不可行子树。2、程序代码#include#includeusingnamespacestd;classMachine{//机器类publ

3、ic:MachineO{//构造函数cw=cc=0;minw=1000;ifstreamin("i叩ut.txt");//从文件输入in»n>>m»d;bestprovider=newint[m+l];//初始化最优供应商和供应商数组provider=newint[ni+1];c=newdouble[n+l];//创建部件价格二维数组for(i=l;i〈=n;i++)c[i]=newdouble[m+l];for(i=l;i<=n;i++)//从文件渎入价格for(intj=l;j<=m;j++)in〉〉c[i][j]

4、;//创逑部件東量二维数组w=newd()uble[n+l];for(i=l;i〈=n;i++)[i]=ncwdouble[m+l];for(i=l;i<=n;i++)//从文件读入重量for(intj=l;j<=m;j++)in»w[i][j];voidBacktrack(inti){if(i〉n){//己得到一个可行解if(cw〈minw){//更新最小重量mimv-cw;for(intj=l;j<=m;j++)bestprovider[j]二provider[j];}return;for(intj=l;j<=m;

5、j++){provider[i]二j;//考虑第j个供应商cc+=c[i][j];cw+=w[i][j];//满足限定条件并且满足限界条件，则递归下一层if(cc<=d&&cw

6、';cout<

7、ach.Output();return0;3、运行截图1）程序所在文件夹有input,txt,运行完成后产生了output,txtDebugtjinputtxtoutput.txt最小重垦机器设计冋監xpp最小重垦机器设计间g.dsp_最小雪垦机嚣设计冋E.ncb_最小重垦机器设计间琵.opt_最小雪垦机嚣设计冋E.plg2）输入文件input,txt第一行分别是部件数量n，供应商数量m，和最大费用d;紧接着输入一个n行m列的部件价格数组和一个n行m列的部件重量数组。邏input.txt•享本文件(F)顚(E)格式(0

8、3341233212221233212223)运行程序后，打开ouput.txt,输出结果如下:output.txt-记事本文件(F)騎E)格式(O)查看(V)4131Dos界面运行如下:<■忏:我的匚++職算法册与分析5-31131Pressanykeytocontinue二、算法实现题5-13工作分配问题设有n件工作分配给