(完整word版)最小重量机器设计问题
最小重量机器设计问题
1。 问题描述
设某一机器由n个部件组成，每一个部件都可以从m个不同的 供应商处购得。设wij是从供应商j处购得的部件i的重量，cij 是相应的价格。试设计一个算法，给出总价格不超过c的最小重 量机器设计.
算法设计:对于给定的机器部件重量和机器部件价格，计算总价 格不超过d的最小重量机器设计。
2. 算法流程分析
设开始时bestx=［-1,—1,…,—1]则相应的排列树由x[0：n—1] 的所有排列构成。
找最小重量机器设计的回溯算法Backtrack是类machine的公 有成员。私有数据成员整型数组Savex保存搜索过的路径，到达 叶节点后将数据赋值给数组bestx。成员bestw记录当前最小重 量,cc表示当前花费，cw表示当前的重量。
在递归函数Backtrack中，在保证总花费不超过c的情况下： 当i=n时，当前扩展结点是排列树的叶节点。此时搜索到一个解， 判断此时的最小重量是否小于当前最小重量,若小于则更新bestw, 并得到搜索路径bestx.
当i〈n时，当前扩展结点位于排列树的第i—1层.当x[0:i] 的花费小于给定最小花费时,算法进入排列树的第i层,否则将减
(完整word版)最小重量机器设计问题
去相应的子树。算法用变量cc记录当前路径x[0：i］的费用。 3。 算法正确性证明
通过几组实例证明合法的输入可以得到正确的输出.实例见附录第2部分。
4. 算法复杂度分析
时间复杂度是 O（n2） 5.参考文献
［1] 王晓东编著，计算机算法设计与分析(第4版）。北京：电子工业出版社，2012。2 6。附录
（1）可执行代码如下: #includeint n; //部件个数 int m； //供应商个数 int COST; //题目中的C int cw; //当前的重量 int cc； //当前花费 int bestw; //当前最小重量 int bestx［N］; int savex［N］;(完整word版)最小重量机器设计问题
int w[N]［N］； int c[N］[N];
public:
MinWmechine(）;
void machine_plan（int i）; void prinout（）; };
MinWmechine：:MinWmechine（） ｛
cw=0; //当前的重量 cc=0; //当前花费
bestw=-1； //当前最小重量 bestx[N]; savex[N］；
cout<<”请输入部件个数：\"； cin〉〉n；
cout〈〈”请输入供应商个数：\"; cin>〉m；
cout<<”请输入总价格不超过：\"; cin>〉COST； for(int j=0;jfor（int i=0;i〈n；i++）(完整word版)最小重量机器设计问题
{
cout〈〈\"请输入第 \"〈〈j+1〈<\" 个供应商的第 \"〈〈i+1<〈” 个部件的重量：”;
cin>>w[i]［j];
cout〈〈”请输入第 ”〈cin〉>c［i]［j]；if（w［i][j]〈0 ｜｜ c[i][j]<0） ｛
cout〈<\"重量或价钱不能为负数!\\n\"; i=i—1； } } ｝ }
void MinWmechine::machine_plan(int i) ｛ if（i>=n) ｛
if(cw 〈bestw ｜| bestw==—1） {
bestw=cw；
for（int j=0;j〈n; j++) //把当前搜过的路径记下来 savex［j]=bestx[j］；
(完整word版)最小重量机器设计问题
｝ return； }
for(int j=0; jif（cc+c［i]［j］〈COST） {cc+=c［i][j]; cw+=w［i][j]; bestx［i]=j；
machine_plan（i+1)； bestx[i]=-1； cc-=c［i]［j]； cw—=w[i］［j]; ｝ ｝ ｝
void MinWmechine：:prinout（) ｛
int i，j，ccc=0; for（j=0;j〈m;j++） {
for(i=0;i〈n；i++) ｛
(完整word版)最小重量机器设计问题
cout<〈\"第 ”<for(j=0; jbestx[j］=-1; ｝ machine_plan(0);cout<<”\\n最小重量机器的重量是： \"〈cout<<\" 第 \"〈〈k+1〈〈\" 部件来自供应商 ”〈cout〈〈\"\\n该机器的总价钱是: \"<〈ccc<int main（void) ｛MinWmechine Y； Y。prinout(）; return 0; }
(完整word版)最小重量机器设计问题
（2）输入输出实例