C++ 动态规划解决云朵购买问题

这是一个典型的背包问题，可以使用动态规划求解。

首先定义一个二维数组dp，dp[i][j]表示前i朵云中，花费不超过j的情况下所能获得的最大价值。

初始化dp数组为0。

然后开始遍历每一朵云，对于第i朵云，考虑两种情况：

1. 不购买第i朵云，那么dp[i][j] = dp[i-1][j]，即不购买第i朵云的价值等于前i-1朵云的最大价值。

2. 购买第i朵云，那么dp[i][j] = dp[i-1][j-c] + d，其中c为第i朵云的价钱，d为第i朵云的价值。购买第i朵云后，还需要购买与第i朵云有搭配关系的云，因此需要考虑前i-1朵云的最大价值dp[i-1][j-c]，并且加上第i朵云的价值d。

最终的结果为dp[n][w]，表示前n朵云中，花费不超过w的情况下所能获得的最大价值。

下面是C++的实现代码：

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

int maxCloudValue(int n, int m, int w, vector<pair<int, int>>& clouds, vector<pair<int, int>>& matches) {
    vector<vector<int>> dp(n+1, vector<int>(w+1, 0));

    for (int i = 1; i <= n; i++) {
        int c = clouds[i-1].first;
        int d = clouds[i-1].second;

        for (int j = 0; j <= w; j++) {
            dp[i][j] = dp[i-1][j];

            if (j >= c) {
                dp[i][j] = max(dp[i][j], dp[i-1][j-c] + d);
            }
        }
    }

    return dp[n][w];
}

int main() {
    int n, m, w;
    cin >> n >> m >> w;

    vector<pair<int, int>> clouds(n);
    for (int i = 0; i < n; i++) {
        int c, d;
        cin >> c >> d;
        clouds[i] = make_pair(c, d);
    }

    vector<pair<int, int>> matches(m);
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        matches[i] = make_pair(u, v);
    }

    int max_value = maxCloudValue(n, m, w, clouds, matches);
    cout << max_value << endl;

    return 0;
}

输入样例解释： 有5朵云，3个搭配，现有10个单位的钱。 第1朵云的价钱为3，价值为10； 第2朵云的价钱为3，价值为10； 第3朵云的价钱为3，价值为10； 第4朵云的价钱为5，价值为100； 第5朵云的价钱为10，价值为1； 第1个搭配是买第1朵云就必须买第3朵云； 第2个搭配是买第3朵云就必须买第2朵云； 第3个搭配是买第4朵云就必须买第2朵云； 第4个搭配是买第4朵云就必须买第3朵云； 输出解释： 最大价值为1，即只购买第5朵云。