小重量机器设计问题.doc

最小重量机器设计问题1. 问题描述 设某一机器由n个部件组成，每一个部件都可以从m个不同的 供应商处购得。设wij是从供应商j处购得的部件i的重量，cij 是相应的价格。试设计一个算法，给出总价格不超过c的最小重 量机器设计。 算法设计：对于给定的机器部件重量和机器部件价格，计算总价 格不超过d的最小重量机器设计。2. 算法流程分析 设开始时bestx=-1,-1,-1则相应的排列树由x0:n-1 的所有排列构成。 找最小重量机器设计的回溯算法Backtrack是类machine的公 有成员。私有数据成员整型数组Savex保存搜索过的路径，到达 叶节点后将数据赋值给数组bestx。成员bestw记录当前最小重 量，cc表示当前花费，cw表示当前的重量。 在递归函数Backtrack中，在保证总花费不超过c的情况下： 当i=n时，当前扩展结点是排列树的叶节点。此时搜索到一个解， 判断此时的最小重量是否小于当前最小重量，若小于则更新bestw， 并得到搜索路径bestx。 当in时，当前扩展结点位于排列树的第i-1层。当x0:i 的花费小于给定最小花费时，算法进入排列树的第i层，否则将减 去相应的子树。算法用变量cc记录当前路径x0:i的费用。3. 算法正确性证明通过几组实例证明合法的输入可以得到正确的输出。实例见附录第2部分。4. 算法复杂度分析 时间复杂度是 O(n2)5.参考文献1 王晓东编著，计算机算法设计与分析（第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();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;（2）输入输出实例