A40994. 最小重量机器设计问题
填空题
中等
知识点
题目描述
最小重量机器设计问题
题目描述
设某一机器由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
参考答案
#include<stdio.h>
#define max 100
int cost[max][max],weight[max][max];
int n,m,d;
int current_weight,current_cost;
int best_cost,best_weight;
int array[max],best_array[max];
void print()
{
printf("%d---%d\n",best_weight,best_cost);
for(int i=1;i<=n;i++)
printf("%d ",best_array[i]);
printf("\n");
}
void BackTrack(int level)
{
if(current_cost>d)
return;
if(level == n+1)
{
if(current_cost<=d&¤t_weight<best_weight)
{
best_cost = current_cost;
best_weight = current_weight;
for(int i=1;i<=n;i++)
best_array[i] = array[i];
}
}
else
{
int i,j,k,l;
for(i=1;i<=m;i++)
{
current_weight = current_weight+weight[level][i];
current_cost = current_cost+cost[level][i];
array[level] = i;
BackTrack(level+1);
current_weight = current_weight-weight[level][i];
current_cost = current_cost-cost[level][i];
}
}
}
int main()
{
int i,j,k,l;
while(scanf("%d%d%d",&n,&m,&d)!=EOF)
{
for(i=1;i<=n;i++)
{
for(j=1;j<=m;j++)
scanf("%d",&cost[i][j]);
}
for(i=1;i<=n;i++)
{
for(j=1;j<=m;j++)
scanf("%d",&weight[i][j]);
}
best_weight = 99999;//max_value;
BackTrack(1);
print();
}
return 0;
}
上一题
下一题