#include<stdio.h> #define MAXN 102 #define MAXM 102 //问题表示 int n; //部件数 int m; //供应商数 int cost; //限定价格 int w[MAXN][MAXM]; //w[i][j]为第i个零件在第j个供应商的重量 int c[MAXN][MAXM]; //c[i][j]为第i个零件在第j个供应商的价格 //求解结果表示 int bestx[MAXN]; int x[MAXN]; int cw=0,cc=0; int bestw=999999; bool find(int i,int j) //如果j在x[1..i-1]中出现，返回true，否则返回false { for (int k=1;k<i;k++) if (x[k]==j) return true; return false; } void dfs(int i) //求解算法 { /*补齐代码*/ } int main() { int i,j; scanf("%d%d%d",&n,&m,&cost); //输入部件数,供应商数,限定价格 for(i=1; i<=n; i++) //输入各部件的在不同供应商的重量 for(j=1; j<=m; j++) scanf("%d",&w[i][j]); for(i=1; i<=n; i++) //输入各部件的在不同供应商的价格 for(j=1; j<=m; j++) scanf("%d",&c[i][j]); dfs(1); //i从1开始搜索 for(i=1;i<=n;i++) //输出每个部件的供应商 printf("%d ",bestx[i]); printf("\n%d\n",bestw); //输出最小重量 return 0; } Dfs（int i）函数的完成代码如下： void dfs(int i) //求解算法 { /*补齐代码*/ }

void dfs(int i) {
if (i > n) { //搜索到第n+1个部件，更新最优解
if (cw < bestw) {
bestw = cw;
for (int j = 1; j <= n; j++)
bestx[j] = x[j];
}
return;
}
for (int j = 1; j <= m; j++) { //枚举第i个部件的供应商
if (c[i][j] <= cost && !find(i, j)) { //价格不超过限定价格且该供应商未选择过
x[i] = j;
cc += c[i][j];
cw += w[i][j];
dfs(i + 1);
cc -= c[i][j];
cw -= w[i][j];
x[i] = 0;
}
}
}