设某一机器由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,m,d,minweight=1000000,curvalue,curweight;
int w[101][101],c[101][101],x[101],bestx[101];
//w[i][j]表示从供应商j处购得的部件i的重量
//c[i][j]是对应的价格，d是限制的总价格
void backtrack(int t){
if(t>n){
if(curweight<minweight){
minweight=curweight;
for(int j=1;j<=n;j++){
bestx[j]=x[j]; //更新最优解所对应的供应商情况
}
}
}
for(int j=1;j<=m;j++){ //注意列数j是供应商
if(curvalue+c[t][j]<=d&&curweight+w[t][j]<minweight){
//保证最小重量&&总价格不超过d
curvalue=curvalue+c[t][j]; //更新状态
curweight=curweight+w[t][j];
x[t]=j; //记录购买每个零件的供应商
backtrack(t+1); //继续进行深度优先搜索
curvalue=curvalue-c[t][j]; //回溯
curweight=curweight-w[t][j];
}
}
}
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<<minweight<<endl;
for(int i=1;i<=n;i++){
cout<<bestx[i]<<" ";
}
return 0;
}
1.1 说明“最小重量机器设计问题"的解空间
（1，1，1）（1，1，2）（1，1，3）
（1，2，1）（1，2，2）（1，2，3）
（1，3，1）（1，3，2）（1，3，3）
（2，1，1）（2，1，2）（2，1，3）
（2，2，1）（2，2，2）（2，2，3）
（2，3，1）（2，3，2）（2，3，3）
（3，1，1）（3，1，2）（3，1，3）
（3，2，1）（3，2，2）（3，2，3）
（3，3，1）（3，3，2）（3，3，3）
1.2 说明 “最小重量机器设计问题"的解空间树
1.3 在遍历解空间树的过程中，每个结点的状态值是什么
当前的重量cw和价格cv