最小重量机器设计问题.doc

最小重量机器设计问题
1.问题描述
设某一机器由n个部件组成，每一个部件都可以从m个不同的
供应商处购得。设wij是从供应商j处购得的部件i的重量，cij
是相应的价格。试设计一个算法，给出总价格不超过c的最小重
量机器设计。
算法设计：对于给定的机器部件重量和机器部件价格，计算总价
格不超过d的最小重量机器设计。
算法流程分析
设开始时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层，否则将减
去相应的子树。算法用变量cc记录当前路径x[0:i]的费用。
3.算法正确性证明
通过几组实例证明合法的输入可以得到正确的输出。实例见附录第2部分。
算法复杂度分析
时间复杂度是O(n2)
5.参考文献
[1]王晓东编著，计算机算法设计与分析（第4版）。北京：电子工业出版社，2012.2
6.附录
（1）可执行代码如下：
#include<iostream>
usingnamespacestd;
#defineN50
classMinWmechine
{
intn;//部件个数
intm;//供应商个数
intCOST;//题目中的C
intcw;//当前的重量
intcc;//当前花费
intbestw;//当前最小重量
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>>COST;
for(intj=0;j<m;j++)
{
for(inti=0;i<n;i++)
{
cout<<"请输入第"<<j+1<<"个供应商的第"<<i+1<<"个部件的重量：";
cin>>w[i][j];
cout<<"请输入第"<<j+1<<"个供应商的第"<<i+1<<"个部件的价格：";
cin>>c[i][j];
if(w[i][j]<0||c[i][j]<0)
{
cout<<"重量或价钱不能为负数！\n";
i=i-1;
}
}
}
}
voidMinWmechine::machine_plan(inti)
{
if(i>=n)
{
if(cw<bestw||bestw==-1)
{
bestw=cw;
for(intj=0;j<n;j++)//把当前搜过的路径记下来
savex[j]=bestx[j];
}
return;
}
for(intj=0;j<m;j++)//依次递归尝试每个供应商
{
if(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];
}
}
}
voidMinWmechine::prinout()
{
inti,j,ccc=0;
for(j=0;j<m;j++)
{
for(i=0;i<n;i++)
{
cout<<"第"<<j+1<<"供应商的第"<<i+1<<"部件重量："<<w[i][j]<<"价格："<<c[i][j]<<"\n";
}
}
for(j=0;j<n;j++)
{
bestx[j]=-1;
}
machine_plan(0);
cout<<"\n最小重量机器的重量是:"<<bestw<<endl;
for(intk=0;k<n;k++)
{
cout<<"第"<<k+1<<"部件来自供应商"<<savex[k]+1<<"\n";
ccc+=c[k][savex[k]];
}
cout<<"\n该机器的总价钱是