欢迎来到天天文库
浏览记录
ID:40563905
大小:131.50 KB
页数:6页
时间:2019-08-04
《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。若peer3、能有比当前最小重量部件选择更好的解,故可将此结点舍去。若在一结点所计算的花费大于所给的最小花费,则剪去以此节点为根的子树。二、算法设计(步骤)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;//当前花费intbestw5、;//当前最小重量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>>COS6、T;for(intj=0;j>w[i][j];cout<<"请输入第"<>c[i][j];if(w[i][j]<07、8、c[i][j]<0){cout<<"重量或价钱不能为负数!";i=i-1;}}}}voidMinWmechine::machine_plan(inti)9、{if(i>=n){if(cw10、11、bestw==-1){bestw=cw;for(intj=0;j12、ti,j,ccc=0;for(j=0;j
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(cw10、11、bestw==-1){bestw=cw;for(intj=0;j12、ti,j,ccc=0;for(j=0;j
10、
11、bestw==-1){bestw=cw;for(intj=0;j12、ti,j,ccc=0;for(j=0;j
12、ti,j,ccc=0;for(j=0;j
此文档下载收益归作者所有