Minimum Weight Machine Design(回溯法).doc

算法设计与分析实验报告实验报告学号： 姓名： 班级：课程名称算法设计与分析实验课时2实验项目最小机器重量设计问题实验时间实验目的 设某一机器由 n 个部件组成，每一种部件都可以从 m 个不同的供应商处购得。设 ij w 是从供应商 j 处购得的部件 i 的重量， ijc是相应的价格。 试设计一个算法，给出总价格不超过 c 的最小重量机器设计。实验环境Visual C+ 实验内容（算法、程序、步骤和方法）实验内容（算法、程序、步骤和方法）实验内容（算法、程序、步骤和方法）实验内容（算法、程序、步骤和方法）实验内容（算法、程序、步骤和方法）实验内容（算法、程序、步骤和方法）1、 算法策略解空间为一棵排列树，采用优先队列式分支限界法找出所给的最小重量机器设计，开始时，将排列树的根节点置为当前扩展结点。在初始扩展结点处还设有选定部件是哪个供应商提供的，故cv=0，cw=0，position=0，peer=0，1in。x1:n记录供应商的选择while完成对排列树内部结点的有序扩展。循环体内依次从活结点优先队列中取出具有最小重量的结点，依次为当前扩展结点。并且花费不超过c并加以扩展，队列为空时则结束循环。当peer=n时，此时扩展结点是叶节点，得到当前的最小重量和最优解数组x。若peerd，则为不可行解，剪去相应子树，返回到i-1层继续执行。 若cw=sum，则不是最优解，剪去相应子树，返回到i-1层继续执行。 若in，则算法搜索到一个叶结点，用sum对最优解进行记录，返回到i-1层继续执行； 用for循环对部件i从m个不同的供应商购得的情况进行选择(1jm）。c.主函数调用一次Knapsack(1)即可完成整个回溯搜索过程，最终得到的sum即为所求最小总重量。代码：#includeusing namespace std;#define N 50class MinWmechineint n; /部件个数int m; /供应商个数int COST; /题目中的Cint cw; /当前的重量int cc; /当前花费int bestw; /当前最小重量int bestxN;int savexN;int wNN;int cNN;public:MinWmechine();void machine_plan(int i);void prinout();MinWmechine:MinWmechine() cw=0; /当前的重量cc=0; /当前花费bestw=-1; /当前最小重量bestxN;savexN;coutn;coutm;coutCOST;for(int j=0;jm;j+) for(int i=0;in;i+) cout请输入第 j+1 个供应商的第 i+1wij;cout请输入第 j+1 个供应商的第i+1cij;if(wij0 | cij0) cout=n) if(cw bestw | bestw=-1)bestw=cw;for(int j=0;jn; j+) /把当前搜过的路径记下来savexj=bestxj; return; for(int j=0; jm; j+) /依次递归尝试每个供应商 if(cc+cijCOST) cc+=cij;cw+=wij;bestxi=j;machine_plan(i+1);bestxi=-1;cc-=cij;cw-=wij; void MinWmechine:prinout()int i,j,ccc=0;for(j=0;jm;j+) for(i=0;in;i+) cout第 j+1 供应商的第 i+1 部件重量： wij价格：cijn; for(j=0; jn; j+) bestxj=-1; machine_plan(0);coutn最小重量机器的重量是: bestwendl;for(int k=0; kn; k+)cout 第 k+1 部件来自供应商savexk+1n;ccc+=cksavexk;coutn该机器的总价钱是: cccendl;coutendl;int main(void) MinWmechine Y; Y.prinout(); return 0;int MinWeightMachine() int i=1,j,wt=0,ct=0; cw=0; cp=0; int besTypep=0; while(1) for(j=1; j=m; j+) wt=cw+wij; ct=cp+cij; if(ct=COST&i=n) if(i=n) int k; if(wtbestw) bestw=wt; for(k=1; kn-1; k+) bestxuliek=bextk+2; bestxulien=j; for(k=1; kn-1; k+) sum+=wkbestxuliek; sum+=wnj; for(k=1; k=n; k+) if(wn-1k=(bestw-sum) bestxulien-1=k; else AddLiveNode(ct,wt,i+1,j); if(bottom=Flag) break; DeleteMin(); cw=N.weight; cp=N.profit; i=N.level; Flag2=N.current; bexti=N.prt; return bestw;int main()int i,j;printf(请输入部件个数n，供应商m和总价COST：);scanf(%d %d %d,&n,&m,&COST);printf(请输入每个物品的价格：);for(i=1; i=n; i+) for(j=1; j=m; j+) scanf(%d,&cij);printf(请输入每个物品的重量：);for(i=1; i=n; i+) for(j=1; j=m; j+) scanf(%d,&wij);printf(最小重量为：n);printf(%dn,MinWeightMachine(); printf(每个物品对应的供应商为:n); for(i=1; i=n; i+) printf(%d ,bestxuliei); return 0;三、复杂度分析 时间复杂度为O(mn) 空间复杂度为O(mn)。数据记录和计算结 论（结 果） 本实验采用的回溯法，对于回溯法，采用深度优先搜索对子集树进行剪枝，剪枝条件是当前的总费用不超过总费用。实验数据正确，该算法设计满足要求。小结实验心得