回溯法-----7-2 最小重量机器设计问题 (25 分)

107 阅读 0 评论 71 点赞

我是靠谱客的博主孝顺篮球，这篇文章主要介绍回溯法-----7-2 最小重量机器设计问题 (25 分)，现在分享给大家，希望可以做个参考。

一、题目：7-2 最小重量机器设计问题 (25 分)

**设某一机器由n个部件组成，每一种部件都可以从m个不同的供应商处购得。设wij 是从供应商j 处购得的部件i的重量，cij是相应的价格。试设计一个算法，给出总价格不超过d的最小重量机器设计。
输入格式:
第一行有3 个正整数n ，m和d， 0<n<30, 0<m<30, 接下来的2n 行，每行n个数。前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>
#include<bits/stdc++.h> 
using namespace std;
int n,m,cost; //限定价格 部件数 供应商数
int w[100][100];//w[i][j]为第i个零件在第j个供应商的重量
int c[100][100];//c[i][j]为第i个零件在第j个供应商的价格
int bestx[100];//bestx[i]用来存放第i个零件的最后选择供应商
int x[100];//x[i]临时存放第i个零件的供应商
int cw=0,cc=0,bestw=100000;
void Backtrack(int t)
// t对应 部件t 
{
if(t>n)//搜索到叶子结点，一个搜索结束，所有零件已经找完
{
if(cw<bestw){
bestw=cw; //当前最小重量
for(int j=1;j<=n;j++)
bestx[j]=x[j];
}
//
return; // 有else就不需要 return，两个选一个 
}
else{
for(int i=1;i<=m;i++)
// 遍历所有供应商 
{
cc+=c[t][i];
cw+=w[t][i];
x[t]=i;
if(cc<=cost && cw<=bestw) // 剪枝操作

Backtrack(t+1);
cc-=c[t][i];
cw-=w[t][i];
}
}
}
int main()
{
cin>>n>>m>>cost;
for(int i=1; i<=n; i++) //各部件在不同供应商的重量 cij:物品i在供应商j的价格 
for(int j=1; j<=m; j++)
cin>>c[i][j];
for(int i=1; i<=n; i++) //各部件在不同供应商的价格 wij:物品i在供应商j的重量 
for(int j=1; j<=m; j++)
cin>>w[i][j];
Backtrack(1);
cout<<bestw<<endl; // 最低的重量 
for(int i=1;i<=n;i++) // 输出各个部件的供应商 
cout<<bestx[i]<<" ";
return 0;
}
/*
测试数据:
3 3 4
1 2 3
3 2 1
2 2 2
1 2 3
3 2 1
2 2 2
*/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64

#include<iostream>
#include<bits/stdc++.h> 
using namespace std;
int n,m,cost; //限定价格 部件数 供应商数
int w[100][100];//w[i][j]为第i个零件在第j个供应商的重量
int c[100][100];//c[i][j]为第i个零件在第j个供应商的价格
int bestx[100];//bestx[i]用来存放第i个零件的最后选择供应商
int x[100];//x[i]临时存放第i个零件的供应商
int cw=0,cc=0,bestw=100000;
void Backtrack(int t)
// t对应 部件t 
{
if(t>n)//搜索到叶子结点，一个搜索结束，所有零件已经找完
{
if(cw<bestw){
bestw=cw; //当前最小重量
for(int j=1;j<=n;j++)
bestx[j]=x[j];
}
//
return; // 有else就不需要 return，两个选一个 
}
else{
for(int i=1;i<=m;i++)
// 遍历所有供应商 
{
cc+=c[t][i];
cw+=w[t][i];
x[t]=i;
if(cc<=cost && cw<=bestw) // 剪枝操作

Backtrack(t+1);
cc-=c[t][i];
cw-=w[t][i];
}
}
}
int main()
{
cin>>n>>m>>cost;
for(int i=1; i<=n; i++) //各部件在不同供应商的重量 cij:物品i在供应商j的价格 
for(int j=1; j<=m; j++)
cin>>c[i][j];
for(int i=1; i<=n; i++) //各部件在不同供应商的价格 wij:物品i在供应商j的重量 
for(int j=1; j<=m; j++)
cin>>w[i][j];
Backtrack(1);
cout<<bestw<<endl; // 最低的重量 
for(int i=1;i<=n;i++) // 输出各个部件的供应商 
cout<<bestx[i]<<" ";
return 0;
}
/*
测试数据:
3 3 4
1 2 3
3 2 1
2 2 2
1 2 3
3 2 1
2 2 2
*/