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

---

w[i][j] 表示供应处 j 部件 i 的重量

c[i][j] 表示供应处 j 部件 i 的价格

weight 表示当前重量，minweight表示最小重量

cost 为当前花费， sumValue 为价格上限

约束条件 cost + c[i][j] < sumValue && weight + w[i][j] < minweight

#include<iostream>
#include<stdio.h>
using namespace std;int n;
int m;
int sumValue;
int weight;
int minweight = 9999;
int cost;
int** c;
int** w;
int* select;	//用来记录分配情况
int* sign;void backtrack(int i)
{if (i > n){minweight = weight;for (int j = 1; j <= n; j++)select[j] = sign[j];}else{for (int j = 1; j <= m; j++){if (cost + c[i][j] <= sumValue && weight + w[i][j] < minweight){sign[i] = j;cost += c[i][j];weight += w[i][j];backtrack(i + 1);cost -= c[i][j];weight -= w[i][j];}}}
}
void initial()
{cout << "请输入部件的数量：";cin >> n;sign = new int[n+1];select = new int[n+1];cout << "请输入供应商的数量：";cin >> m;w = new int*[n+1];for (int i = 1; i <= m; i++)w[i] = new int[m+1];c = new int* [n+1];for (int i = 1; i <= m; i++)c[i] = new int[m+1];cout << "输入部件对应的价值：";for (int i = 1; i <= n; i++){for (int j = 1; j <= m; j++)cin >> c[i][j];}cout << "输入部件对应的重量：";for (int i = 1; i <= n; i++){for (int j = 1; j <= m; j++)cin >> w[i][j];}cout << "请输入总价值：";cin >> sumValue;
}int main()
{initial();backtrack(1);cout << "部件1-" << n << "选择的供应商:" << endl;for (int i = 1; i <= n; i++)cout << select[i] << " ";return 0;
}