最小重量机器问题 设某一机器由 n 个部件组成，每种部件都可以从 m 个不同的供应商处购得。设 Wij 是从供应商 j 处购得的部件 i 的重量，Cij 是相应的价格。试设计一个算法，给出总价格不超过 c 的最小重量机器设计C++编程实现

以下是该问题的C++代码实现：

#include <iostream>
#include <cstring>
using namespace std;

const int INF = 0x3f3f3f3f;

int n, m, c;
int W[105][105], C[105][105];
int dp[105][10005];

int main() {
    cin >> n >> m >> c;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            cin >> W[i][j] >> C[i][j];
        }
    }

    memset(dp, INF, sizeof(dp));
    dp[0][0] = 0;

    for (int i = 1; i <= n; i++) {
        for (int j = 0; j <= c; j++) {
            for (int k = 1; k <= m; k++) {
                if (C[i][k] <= j) {
                    dp[i][j] = min(dp[i][j], dp[i-1][j-C[i][k]] + W[i][k]);
                }
            }
        }
    }

    int ans = 0;
    for (int j = c; j >= 0; j--) {
        if (dp[n][j] <= c) {
            ans = dp[n][j];
            break;
        }
    }

    cout << ans << endl;

    return 0;
}

该算法采用三重循环实现状态转移。时间复杂度为 O(nmc)，空间复杂度为 O(nc)。