算法第五章上机实践报告
问题描述
7-2 最小重量机器设计问题 (25 分)
设某一机器由n个部件组成，每一种部件都可以从m个不同的供应商处购得。设wij是从供应商j 处购得的部件i的重量，cij是相应的价格。 试设计一个算法，给出总价格不超过d的最小重量机器设计。
输入格式:
第一行有3 个正整数n ，m和d， 0<n<30, 0<m<30, 接下来的2n 行，每行m个数。前n行是c，后n行是w。
输出格式:
输出计算出的最小重量，以及每个部件的供应商
输入样例:
3 3 4
1 2 3
3 2 1
2 2 2
1 2 3
3 2 1
2 2 2
结尾无空行
输出样例:
在这里给出相应的输出。例如：
4
1 3 1
代码描述
#include <iostream>
using namespace std;
int n,m,d;
int c[100][100];
int w[100][100];
int cv，cw;
int x[100];
int supplier[100];
int min_m=10000;
void Backtrack(int t){
if(t>n){
if(cw<min_m){
min_m=cw;
for(int i=1;i<=n;i++){
supplier[i]=x[i];
}
}
}
else{
for(int i=1;i<=m;i++){
x[t]=i;
cv+=c[t][i];
cw+=w[t][i];
if(cv<=d&&cw<min_m){
Backtrack(t+1);
}
cv-=c[t][i];
cw-=w[t][i];
}
}
}
int main(){
cin>>n>>m>>d;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
cin>>c[i][j];
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
cin>>w[i][j];
}
}
cw=0;
cv=0;
Backtrack(1);
cout<<min_m<<endl;
for(int i=1;i<=n;i++){
cout<<supplier[i]<<" ";
}
}
1.1 说明“最小重量机器设计问题"的解空间
有n个部件可以有m个不同的供应商获得，所以解空间是n*m
1.2 说明 “最小重量机器设计问题"的解空间树
一共有n层，每一层的节点有m个分支，每一层的m个分支代表从不同供应商得到的零件。
1.3 在遍历解空间树的过程中，每个结点的状态值是什么
当前总重量和当前总价格
- 2. 你对回溯算法的理解
回溯算法是通过对问题的所有可能进行尝试和列举，再把不满足条件的可能去除，最后得到满足所以条件的结果。