一.题目
7-2 最小重量机器设计问题 (25 分)设某一机器由n个部件组成,每一种部件都可以从m个不同的供应商处购得。设wij是从供应商j 处购得的部件i的重量,cij是相应的价格。 试设计一个算法,给出总价格不超过d的最小重量机器设计。
输入格式:
第一行有3 个正整数n ,m和d, 0<n<30, 0<m<30, 接下来的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
二代码#include <iostream>
using
namespace
std;
int
n;
int
m;
int
d;
int
w[1000][1000];
int
c[1000][1000];
int
minw=100000000;
int
curw=0;
int
curc=0;
int
minx[1000];
int
x[1000];
void
backtrack(
int
t){
if
(t>n){
if
(curw<minw){
minw=curw;
for
(
int
i=1; i<=n; i++){
minx[i]=x[i];
}
}
}
else
{
for
(
int
i=1; i<=m; i++){
curc+=c[t][i];
curw+=w[t][i];
x[t]=i;
if
(curc<=d && curw<minw){
backtrack(t+1);
}
curc-=c[t][i];
curw-=w[t][i];
x[t]=0;
}
}
}
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];
}
}
backtrack(1);
cout<<minw<<endl;
for
(
int
i=1; i<=n; i++){
cout<<minx[i]<<
" "
;
}
cout<<endl;
return
0;
}
二理解
回溯法(探索与回溯法)是一种选优搜索法,又称为试探法,按选优条件向前搜索,以达到目标。但当探索到某一步时,发现原先选择并不优或达不到目标,就退回一步重新选择,这种走不通就退回再走的技术为回溯法