---

一、问题描述

 设某一机器由 $n$ 个部件组成，每种部件都可以从 $m$ 个不同的供应商处购得。设 $w_{ij}$ 是从供应商 $j$ 处购得的部件i的重置，$c_{ij}$ 是相应的价格。设计一个算法，给出总价格不超过 $d$ 的最小重量机器设计。

数据输入：
第 $1$ 行有 $3$ 个正整数 $n$，$m$ 和 $d$。接下来的 $2n$ 行，每行 $n$ 个数。前 $n$ 行是 $c$，后 $n$ 行是 $w$。
数据输出：
输出计算的最小重量及每个部件的供应商。

二、算法思路

 1. 采用回溯法。因为每个商品可以从 $m$ 个供货商获得，则问题的解空间树是一棵 $m$ 叉树，该树属于子集树而非排列树。

 2. 然后考虑剪枝条件，此问题中的限制条件为价格上限 $c$，最小重量设 $bestw$，则当前价格 $cc<c$ 且 当前重量 $cw<bestw$ 时，执行树的深度遍历，否则，执行回溯，因此本问题中包含两个剪枝条件。

 3. 最后是更新最优值，以及问题的解，本题中最优解是 $bestw$，解集合是 $x[i]$。递归出口处更新一种最优解，以及对应解集合。

三、代码编写

输入样例：
3 3 4
1 2 3
3 2 1
2 2 2
3 3 4
1 2 3
3 2 1
2 2 2
输出样例：
4
1 3 1

#include<iostream>
using namespace std; 
#define maxn 110int w[maxn][maxn];
int c[maxn][maxn];
int bestx[maxn];
int x[maxn];
int n, m, d;
int cw = 0, cc = 0, bestw = 0x3f3f3f3f;void Backtrack(int t) {if (t > n) {bestw = cw;for (int i = 1; i <= n; i++)bestx[i] = x[i];}else {for (int i = 1; i <= m; i++) {if (cc + c[t][i] <= d && cw + w[t][i] < bestw) {x[t] = i;cc += c[t][i];cw += w[t][i];Backtrack(t + 1);cc -= c[t][i];cw -= w[t][i];}}}
}int main() {cout<<"请依次输入部件数，供应商数，限定价格：" << endl;cin>> n >> m >> d;cout<<"请输入各部件的在不同供应商的重量：" << endl;for (int i = 1; i <= n; i++)for (int j = 1; j <= m; j++)cin>>w[i][j];cout<<"请输入各部件的在不同供应商的价格：" << endl;for (int i = 1; i <= n; i++)for (int j = 1; j <= m; j++)cin>>c[i][j];Backtrack(1);cout<<"最小重量为：" << bestw << endl;cout<<"每个部件的供应商：" << endl;for (int i = 1; i <= n; i++){if(i==1) cout<<bestx[i]<<" "; else cout<<bestx[i]<<" ";}return 0;
}