最小重量机器设计 java_最小重量机器设计问题

问题描述

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

输出输出示例

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

算法分析

这个问题有很多种解决方法，这里我们以分支限界法中的最大收益优先的方式搜索问题的子空间树。以广度优先的思想，把所有当前的活结点放入优先队列中，取出当前重量最小的结点，拓展这个活结点的所有儿子结点并进行剪枝，如果结点深度等于树的高度，就把最优解更新(如果结果没有当前最优解好，在剪枝环节就会减掉，所以这一步不需比较)。当优先队列为空时，说明已经遍历了所有解，输出最优值和最优解。

代码

变量解释：w是从供应商购得部件的重量，c表示部件的价格，ans表示当前最优解，当前购得部件的个数(树的深度)level和结点的编号idx。

e中存储的是当前结点的总价格和总重量，Pre存储的是当前结点的父节点的编号和当前选择的供应商号，优先队列QU中第一个数为结点的重量，第二个数为结点的编号。

#include

using namespace std;

typedef pair PII;

const int N = 110;

int c[N][N], w[N][N], ans[N], level[N * N], idx = 1;

PII e[N * N], Pre[N * N];

priority_queue QU;

int n, m, d, minw = INT_MAX;

void bfs(){

QU.push({0,0}); //初始化

while(!QU.empty()){ //队列为空就跳出循环

PII i = QU.top(); //取堆顶元素

i.first = -i.first; //队列中存的数为重量的相反数，再取反变回重量

QU.pop();

if(e[i.second].first > d || e[i.second].second > minw){

continue; //剪枝，如果当前的价格比要求的高或者解不如当前的最优解就减掉

}

else if(level[i.second] == n + 1){//当深度为n就记录下当前的最优解和最优值

minw = e[i.second].second;

int k = 1;

for(int j = i.second; j != 0; j = Pre[j].first) ans[k ++ ] = Pre[j].second;

}

else{ //拓展当前结点的所有孩子结点,idx为当前新结点的编号

for(int j = 1; j <= m; j ++){

int nc = e[i.second].first + c[level[i.second]][j];

int nw = e[i.second].second + w[level[i.second]][j];

e[idx] = {nc, nw}; //e[idx]中记录新节点的价格和重量

Pre[idx] = {i.second, j};

level[idx] = level[i.second] + 1;

QU.push({-nw, idx});//优先队列默认为大顶堆，所以把重量的相反数输入，就可以构成小顶堆

idx ++;

}

}

}

}

int main()

{

cin >> n >> m >> d;

for(int i = 1; i <= n; i ++)

for(int j = 1; j <= m; j ++)

cin >> c[i][j]; //输入价格c

for(int i = 1; i <= n; i ++)

for(int j = 1; j <= m; j ++)

cin >> w[i][j]; //输入重量w

bfs(); //调用bfs函数

cout << minw << endl; //最优值

//最优解是倒序存储的，所以从后往前进行遍历

for(int i = n; i >= 1; i --) cout << ans[i] << " ";

return 0;

}