2635: 回溯法-最小机器重量设计问题
金币值：3
定数：9
时间限制：1.000 s
内存限制：128 M
正确：2
提交：2
正确率：100.00% 命题人：
题目描述
假设生产一台机器需要n个不同的零件，每个零件可以从m个不同的供应商购买。设wij表示第i个零件从供应商j购买的重量，cij表示第i个零件从供应商j购买的价格。设计一个算法，要求给出总价格不超过d的最小重量机器设计，用回溯法。
测试代码 复制
#include <stdio.h>
int n,m,d; //表示机器有n个零件，每个零件有m个不同的厂家生产，总成本不超过d
int c[100][100]; //成本矩阵，0号单元不用
int w[100][100]; //重量矩阵，0号单元不用
int x[100]; //当前解向量，0号单元不用
int bestx[100]; //最好的解向量，0号单元不用
int cw;//当前重量
int cc;//当前成本
int bestw;//当前最小的机器重量
void input();
void Backtrack(int i);
void input() {
int i, j;
scanf("%d %d %d", &n,&m,&d);
for(i=1; i<=n; i++) {
for(j=1; j<=m; j++) {
scanf("%d", &c[i][j]);
}
}
for(i=1; i<=n; i++) {
for(j=1; j<=m; j++) {
scanf("%d", &w[i][j]);
}
}
}
void Backtrack(int i) {
if(i>n) {
}
else {
for(int j = 1; j <= m; j++) {
}
}
}
int main(void) {
cc=0;
cw=0;
bestw=32767; //假设最大的整数用32767来表示
input();
Backtrack(1);
printf("%d\n",bestw);
for(int i=1; i<=n; i++) printf("%d ",bestx[i]);
return 0;
}输入格式
第1行输入3个整数，分别表示机器零件总的个数n，供应商个数m，以及机器的最大价格d
接下来的n行m列，分别表示第i个零件来自第j个供应商的价格 cij
再接下来的n行m列，分别表示第i个零件来自第j个供应商的重量 wij
接下来的n行m列，分别表示第i个零件来自第j个供应商的价格 cij
再接下来的n行m列，分别表示第i个零件来自第j个供应商的重量 wij
输出格式
第1行输出最小机器重量
第2行输出最小机器重量每个零件的生产厂家编号（从1开始编号）
第2行输出最小机器重量每个零件的生产厂家编号（从1开始编号）
输入样例 复制
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提示
思考：本题是0-1背包问题以及N后问题之间有什么关系？