【算法】求解最小机器重量设计问题回溯法（C++源码）
一、问题描述
设某一机器由n个部件组成，部件编号为1～n，
每一种部件都可以从m个供应商处购得，供应商编号为1～m。
设wij是从供应商j处购得的部件i的重量，cij是相应的价格。
对于给定的机器部件重量和机器部件价格，计算总价格不超过cost的最小重量机器设计，
可以在同一个供应商处购得多个部件。
二、输入描述
第一行输入3个整数n,m,cost，
接下来n行输入wij（每行m个整数）,
最后n行输入cij（每行n个整数）
三、输出描述
输出的第1行包括n个整数，
表示每个对应的供应商编号，
第2行为对应的重量。
四、输入样例
3 3 7
1 2 3
3 2 1
2 3 2
1 2 3
5 4 2
2 1 2
五、输出样例
1 3 1
4
六、步骤描述
n个部件，m个供应商，不超过cost的总价，w[i][j]表示部件i从供应商j得到的重量，x[k]表示装每个零件对应的供应商的编号，深度优先搜索k的重量和价格，未超过则替换相加输出。
七、运行结果截图
八、源代码（C++）
#include <iostream>
using namespace std;
int m, cost;//n个部件，m个供应商，不能超过cost的开销
int w[100][100];//w[i][j]表示部件i从供应商j得到的重量
int c[100][100];
int x[100];//装每个零件对应的供应商的编号
int res[100];
int min_w=0x3f3f3f3f;
int dfs(int k, int weight, int pay)//每次搜第k个部件
{
if(k==4)
{
if(weight<min_w)
{
min_w=weight;
for(int i=0;i<m;i++)
{
res[i]=x[i];
}
}
return 0;
}
else
{
for(int i=0;i<m;i++)
{
if(weight+w[k][i]<min_w && pay+c[k][i]<=cost)
{
x[k]=i;
dfs(k+1,weight+w[k][i],pay+c[k][i]);
x[k]=0;
}
}
}
return 0;
}
int main()
{
int n;
cin>>n>>m>>cost;
for(int i=0;i<n;i++)
{
for(int j=0;j<n;j++)
{
cin>>w[i][j];
}
}
for(int i=0;i<n;i++)
{
for(int j=0;j<n;j++)
{
cin>>c[i][j];
}
}
dfs(1,0,0);
for(int i=0;i<m;i++)
{
cout<<res[i]+1<<" ";
}
cout<<endl;
cout<<min_w+1<<endl;
return 0;
}