(完整word版)最小重量机器设计问题(word文档良心出品)

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

2、成员 bestw 记录当前最小重量，cc表示当前花费，cw表示当前的重量。在递归函数 Backtrack 中，在保证总花费不超过 c 的情况下： 当 i=n 时，当前扩展结点是排列树的叶节点。此时搜索到一个解， 判断此时的最小重量是否小于当前最小重量， 若小于则更新 bestw，并得到搜索路径 bestx 。当 in 时，当前扩展结点位于排列树的第 i-1 层。当 x0:i的费用。去相应的子树。算法用变量 cc 记录当前路径 x0:i3. 算法正确性证明通过几组实例证明合法的输入可以得到正确的输出实例见附录第 2 部分。4. 算法复杂度分析时间复杂度是 O（n 2）5. 参考文献1 王晓东编著

3、，计算机算法设计与分析（第 4 版）。北京：电子工业出版社， 2012.26. 附录1）可执行代码如下：#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()

4、;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;Pprss anpta cart inihefor(int j=0;jn; j+) /把当前搜过的

5、路径记下来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 最小重

6、量机器的重量是 : bestwendl;for(int k=0; kn; k+)自供应商k+1 部件来coutsavexk+1n;ccc+=cksavexk;coutn该机器的总价钱是：cccendl;coute ndl;int mai n(void)Mi nWmechi ne Y;Y.prin out();retur n 0;(2)输入输出实例窝 I Pfdceos File 3 Micro soft Visual StudioMyProj ectsaxDebiig.ax. ore*13421245量啻至啻至啻曙3 2 2 5 ，-cn.-CEl-ol-Qzl-Qzl-fn.,-CCI,-QZLe 卜卜 件件4-件 f-j-l弓弓弓弓 乂口工口忙口尙凋凋14 14 112 2 112 2S=J 2第第第1勺勺勺勺勺勺勺勺-4- UUJ- .UUJ .UUJ A-i XJJ ip JullR r-yw r2_ 2 士商商商商商商商1苛 2应应应应应应应应1212 怦町百个个个个个个个个的的的的 中区11112222商