Minimum Weight Machine Design(回溯法)

《Minimum Weight Machine Design(回溯法)》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、算法设计与分析实验报告实验报告学号：姓名：班级：课程名称算法设计与分析实验课时2实验项目最小机器重量设计问题实验时间实验目的设某一机器由n个部件组成，每一种部件都可以从m个不同的供应商处购得。设ijw是从供应商j处购得的部件i的重量，ijc是相应的价格。试设计一个算法，给出总价格不超过c的最小重量机器设计。实验环境VisualC++实验内容（算法、程序、步骤和方法）一、算法策略解空间为一棵排列树，采用优先队列式分支限界法找出所给的最小重量机器设计，开始时，将排列树的根节点置为当前扩展结点。在初始扩展结点处还设有选定部件是哪个供应商提供的，故cv=

2、0，cw=0，position=0，peer=0，1≤i≤n。x[1:n]记录供应商的选择while完成对排列树内部结点的有序扩展。循环体内依次从活结点优先队列中取出具有最小重量的结点，依次为当前扩展结点。并且花费不超过c并加以扩展，队列为空时则结束循环。当peer=n时，此时扩展结点是叶节点，得到当前的最小重量和最优解数组x。若peer

3、能有比当前最小重量部件选择更好的解，故可将此结点舍去。若在一结点所计算的花费大于所给的最小花费，则剪去以此节点为根的子树。二、算法设计（步骤）a.部件有n个，供应商有m个，分别用w[i][j]和c[i][j]存储从供应商j处购得的部件i的重量和相应价格，d为总价格的上限。 b.用递归函数backtrack(i)来实现回溯法搜索排列树（形式参数i表示递归深度）。 ①若cp>d，则为不可行解，剪去相应子树，返回到i-1层继续执行。 ②若cw>=sum，则不是最优解，剪去相应子树，返回到i-1层继续执行。 ③若i>n，则算法搜索到一个叶结点，用sum对

4、最优解进行记录，返回到i-1层继续执行； ④算法设计与分析实验报告实验内容（算法、程序、步骤和方法）用for循环对部件i从m个不同的供应商购得的情况进行选择(1≤j≤m）。 c.主函数调用一次Knapsack(1)即可完成整个回溯搜索过程，最终得到的sum即为所求最小总重量。 代码：#includeusingnamespacestd;#defineN50classMinWmechine{intn;//部件个数intm;//供应商个数intCOST;//题目中的Cintcw;//当前的重量intcc;//当前花费intbestw

5、;//当前最小重量intbestx[N];intsavex[N];intw[N][N];intc[N][N];public:MinWmechine();voidmachine_plan(inti);voidprinout();};MinWmechine::MinWmechine(){cw=0;//当前的重量cc=0;//当前花费bestw=-1;//当前最小重量bestx[N];savex[N];cout<<"请输入部件个数：";cin>>n;cout<<"请输入供应商个数：";cin>>m;cout<<"请输入总价格不超过：";cin>>COS

6、T;for(intj=0;j>w[i][j];cout<<"请输入第"<>c[i][j];if(w[i][j]<0

7、

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

9、{if(i>=n){if(cw

10、

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

12、ti,j,ccc=0;for(j=0;j