最小重量机器设计问题

《最小重量机器设计问题》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、最小重量机器设计问题1.问题描述设某一机器由n个部件组成，每一个部件都可以从m个不同的供应商处购得。设wij是从供应商j处购得的部件i的重量，cij是相应的价格。试设计一个算法，给出总价格不超过c的最小重量机器设计。算法设计：对于给定的机器部件重量和机器部件价格，计算总价格不超过d的最小重量机器设计。2.算法流程分析设开始时bestx=[-1,-1,…,-1]则相应的排列树由x[0:n-1]的所有排列构成。找最小重量机器设计的回溯算法Backtrack是类machine的公有成员。私有数据成员整型数组Savex保存搜索过的路径，到达叶节点后将数据赋值给数组bestx。成员bestw记

2、录当前最小重量，cc表示当前花费，cw表示当前的重量。在递归函数Backtrack中，在保证总花费不超过c的情况下：当i=n时，当前扩展结点是排列树的叶节点。此时搜索到一个解，判断此时的最小重量是否小于当前最小重量，若小于则更新bestw，并得到搜索路径bestx。当i

3、晓东编著，计算机算法设计与分析（第4版）。北京：电子工业出版社，2012.26.附录（1）可执行代码如下：#includeusingnamespacestd;#defineN50classMinWmechine{intn;//部件个数intm;//供应商个数intCOST;//题目中的Cintcw;//当前的重量intcc;//当前花费intbestw;//当前最小重量intbestx[N];intsavex[N];intw[N][N];intc[N][N];public:MinWmechine();voidmachine_plan(inti);voidprino

4、ut();};MinWmechine::MinWmechine(){cw=0;//当前的重量cc=0;//当前花费bestw=-1;//当前最小重量bestx[N];savex[N];cout<<"请输入部件个数：";cin>>n;cout<<"请输入供应商个数：";cin>>m;cout<<"请输入总价格不超过：";cin>>COST;for(intj=0;j>w[i][j];cout<<"请输入第"<

5、>c[i][j];if(w[i][j]<0

6、

7、c[i][j]<0){cout<<"重量或价钱不能为负数！";i=i-1;}}}}voidMinWmechine::machine_plan(inti){if(i>=n){if(cw

8、

9、bestw==-1){bestw=cw;for(intj=0;j

10、][j];bestx[i]=j;machine_plan(i+1);bestx[i]=-1;cc-=c[i][j];cw-=w[i][j];}}}voidMinWmechine::prinout(){inti,j,ccc=0;for(j=0;j

11、endl;for(intk=0;k