【分支限界法】最小重量机器设计问题

133 阅读 0 评论 88 点赞

我是靠谱客的博主无情水蜜桃，这篇文章主要介绍【分支限界法】最小重量机器设计问题，现在分享给大家，希望可以做个参考。

算法实现题 6-4 最小重量机器设计问题

问题描述：设某一机器由n个部件组成，每一种部件都可以从m个不同的供应商处购得。设wij是从供应商j处购来的部件i的重量，cij是相应的价格。
设计一个优先队列式分支定界法，给出总价格不超过c的最小重量机器设计。
算法设计：对于给定的机器部件重量和机器部件价格，设计一个优先队列式分支定界法，计算总价值不超过d的最小重量机器设计。

数据输入：第一行由3个正整数n，m，d。接下来的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

参考链接：https://blog.csdn.net/qq_43510916/article/details/109760741

慎看！！！

不会写，几乎全抄。。。

复制代码

#include<bits/stdc++.h>
using namespace std;
int n,m,d,minW=99999;
int c[999][999],w[999][999];//c[i][j],w[i][j] 各表示从供应商j处购得部件i的价格/重量
int ans[999];//存储最优排序结果
struct stu {
int weight,cost,level,num,value[999];
stu(int a,int b,int c,int d):weight(a),cost(b),level(c),num(d) {}
bool operator<(const stu& a) const {
if(weight!=a.weight)
return weight>a.weight;
else if(level!=a.level)
return level>a.level;
else
return num>a.num;
}
};
priority_queue<stu> q;//小顶堆
int main() {
cin>>n>>m>>d;
for(int i=0; i<n; i++)
for(int j=0; j<m; j++)
cin>>c[i][j];
for(int i=0; i<n; i++)
for(int j=0; j<m; j++)
cin>>w[i][j];
for(int i=0; i<m; i++) {
stu t=stu(w[0][i],c[0][i],0,i);
if(t.cost<=d) { //利用价格剪枝
t.value[0]=i+1;
q.push(t);
}
}
while(!q.empty()) {
stu temp=q.top();
q.pop();
if(temp.level<n-1) {
for(int i=0; i<m; i++) {
stu t=stu(temp.weight+w[temp.level+1][i],temp.cost+c[temp.level+1][i],temp.level+1,i);
if(t.level==n-1) {
if(t.weight<minW&&t.cost<=d) {//剪枝
minW=t.weight;
for(int i=0; i<n-1; i++)
ans[i]=temp.value[i];
ans[n-1]=i+1;
}
}
if(t.level<n-1) {
if(t.cost<=d) {//剪枝
for(int i=0; i<t.level; i++)
t.value[i]=temp.value[i];
t.value[t.level]=i+1;
q.push(t);
}
}
}
}
}
cout<<minW<<endl;
for(int i=0; i<n; i++)
cout<<ans[i]<<" ";
return 0;
}
/*
输入：
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
输入：
8 18 14
18 15 20 5 15 10 16 6 1 6 17 6 1 2 17 15 13 17
16 6 7 4 7 2 11 6 18 4 13 12 8 5 2 8 15 14
12 6 19 10 13 8 2 10 16 4 15 15 16 13 17 12 14 4
18 18 2 13 15 19 5 12 18 7 13 9 8 17 10 13 15 11
8 5 14 11 18 20 17 3 11 17 13 11 4 9 17 14 19 1
10 7 8 11 13 3 19 3 12 11 12 14 4 2 12 10 14 15
12 9 13 9 16 17 12 15 6 3 11 17 13 17 14 13 4 4
19 12 3 19 3 20 19 12 8 19 8 10 19 20 3 1 7 1
16 12 4 16 2 6 15 1 13 3 7 16 5 3 16 16 14 19
12 14 6 2 11 15 9 17 15 16 19 20 14 14 20 9 4 4
6 13 16 6 3 12 12 19 11 20 4 13 9 18 7 17 8 1
4 17 3 20 3 8 12 7 4 12 6 12 1 18 13 20 20 8
4 15 1 10 2 12 8 11 5 4 20 13 12 20 1 3 3 11
1 9 2 1 16 1 12 4 5 2 7 15 12 3 9 4 13 6
13 1 10 8 5 13 20 10 6 4 8 15 8 8 20 11 9 9
2 10 11 1 18 8 20 11 18 2 3 6 14 16 19 4 3 15
输出：
57
13 6 7 3 18 14 10 16
*/

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
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
#include<bits/stdc++.h>
using namespace std;
int n,m,d,minW=99999;
int c[999][999],w[999][999];//c[i][j],w[i][j] 各表示从供应商j处购得部件i的价格/重量
int ans[999];//存储最优排序结果
struct stu {
int weight,cost,level,num,value[999];
stu(int a,int b,int c,int d):weight(a),cost(b),level(c),num(d) {}
bool operator<(const stu& a) const {
if(weight!=a.weight)
return weight>a.weight;
else if(level!=a.level)
return level>a.level;
else
return num>a.num;
}
};
priority_queue<stu> q;//小顶堆
int main() {
cin>>n>>m>>d;
for(int i=0; i<n; i++)
for(int j=0; j<m; j++)
cin>>c[i][j];
for(int i=0; i<n; i++)
for(int j=0; j<m; j++)
cin>>w[i][j];
for(int i=0; i<m; i++) {
stu t=stu(w[0][i],c[0][i],0,i);
if(t.cost<=d) { //利用价格剪枝
t.value[0]=i+1;
q.push(t);
}
}
while(!q.empty()) {
stu temp=q.top();
q.pop();
if(temp.level<n-1) {
for(int i=0; i<m; i++) {
stu t=stu(temp.weight+w[temp.level+1][i],temp.cost+c[temp.level+1][i],temp.level+1,i);
if(t.level==n-1) {
if(t.weight<minW&&t.cost<=d) {//剪枝
minW=t.weight;
for(int i=0; i<n-1; i++)
ans[i]=temp.value[i];
ans[n-1]=i+1;
}
}
if(t.level<n-1) {
if(t.cost<=d) {//剪枝
for(int i=0; i<t.level; i++)
t.value[i]=temp.value[i];
t.value[t.level]=i+1;
q.push(t);
}
}
}
}
}
cout<<minW<<endl;
for(int i=0; i<n; i++)
cout<<ans[i]<<" ";
return 0;
}
/*
输入：
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
输入：
8 18 14
18 15 20 5 15 10 16 6 1 6 17 6 1 2 17 15 13 17
16 6 7 4 7 2 11 6 18 4 13 12 8 5 2 8 15 14
12 6 19 10 13 8 2 10 16 4 15 15 16 13 17 12 14 4
18 18 2 13 15 19 5 12 18 7 13 9 8 17 10 13 15 11
8 5 14 11 18 20 17 3 11 17 13 11 4 9 17 14 19 1
10 7 8 11 13 3 19 3 12 11 12 14 4 2 12 10 14 15
12 9 13 9 16 17 12 15 6 3 11 17 13 17 14 13 4 4
19 12 3 19 3 20 19 12 8 19 8 10 19 20 3 1 7 1
16 12 4 16 2 6 15 1 13 3 7 16 5 3 16 16 14 19
12 14 6 2 11 15 9 17 15 16 19 20 14 14 20 9 4 4
6 13 16 6 3 12 12 19 11 20 4 13 9 18 7 17 8 1
4 17 3 20 3 8 12 7 4 12 6 12 1 18 13 20 20 8
4 15 1 10 2 12 8 11 5 4 20 13 12 20 1 3 3 11
1 9 2 1 16 1 12 4 5 2 7 15 12 3 9 4 13 6
13 1 10 8 5 13 20 10 6 4 8 15 8 8 20 11 9 9
2 10 11 1 18 8 20 11 18 2 3 6 14 16 19 4 3 15
输出：
57
13 6 7 3 18 14 10 16
*/