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

最小重量机器设计问题
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层，否则将减
去相应的子树。算法用变量cc记录当前路径x[0:i]的费用。
3. 算法正确性证明
通过几组实例证明合法的输入可以得到正确的输出。实例见附录第2部分。
4. 算法复杂度分析
时间复杂度是 O(n2)
5.参考文献
[1] 王晓东编著，计算机算法设计与分析（第4版）。北京：电子工业出版社，2012.2
6.附录
（1）可执行代码如下：
#include<iostream>
using namespace std;
#define N 50
class MinWmechine
{
int n; //部件个数
int m; //供应商个数
int COST; //题目中的C
int cw; //当前的重量
int cc; //当前花费
int bestw; //当前最小重量
int bestx[N];
int savex[N];
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;j<m;j++)
{
for(int i=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;
}
}
}
}
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];
}
return;
}
for(int j=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];
}
}
}
void MinWmechine::prinout()
{
int i,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(int k=0; k<n; k++)
{
cout<<" 第 "<<k+1<<" 部件来自供应商 "<<savex[k]+1<<"\n";
ccc+=c[k][savex[k]];
}
cout<<"\n该机器的总价钱是: "<<ccc<<endl;
cout<<endl;
}
int main(void)
{
MinWmechine Y;
Y.prinout();
return 0;
}
（2）输入输出实例