4. 最小重量机器设计

69 阅读 0 评论 46 点赞

我是靠谱客的博主搞怪嚓茶，最近开发中收集的这篇文章主要介绍4. 最小重量机器设计，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

【问题描述】

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

【输入形式】

第一行有3个正整数n , m , d 。接下来的2n 行，每行n个数。前n行是c ，后n 行是w

【输出形式】

最小重量及每个部件的供应商

【样例输入】

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

#include<bits/stdc++.h>
using namespace std;
const int N=500;

int n,m,d;

int a[N],temp_a[N];  //选择的供应商
int w[N][N],c[N][N];
int ans=10000;

void dfs(int count,int va,int temp_ans)
{
	if(count>n)
	{
		ans=min(ans,temp_ans);
		for(int i=1;i<=m;i++) a[i]=temp_a[i];
	}
	else
	{
		for(int i=1;i<=m;i++)
		{
			if(va+c[count][i]<=d && temp_ans+w[count][i]<=ans)
			{
				temp_a[count]=i;
				dfs(count+1,va+c[count][i],temp_ans+w[count][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];
		}
	}
	dfs(1,0,0);
	cout<<ans<<endl;
	for(int i=1;i<=n;i++) cout<<a[i]<<" ";
}