#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; }

这是一道经典的01背包问题，但是与普通的01背包问题不同，这里的物品是具有供应商限制的，即每个物品只能从特定的一些供应商中选择。

算法思路：

使用DFS搜索，对于每个部件，枚举其可以选择的供应商，如果该供应商未被选择过且价格不超过限定价格，则选择该供应商并继续搜索下一个部件；如果所有供应商都已经被选择过或者价格超过限定价格，则回溯到上一个部件，尝试选择其他的供应商。搜索到第n+1个部件时，更新最优解。

代码实现：

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;
        }
    }
}