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

这道题可以使用动态规划来解决。首先，我们定义一个长度为n的数组dp，dp[i]表示当拥有i元钱时可以获得的最大价值。我们可以初始化dp数组为0。

然后，我们遍历每一朵云，对于每一朵云，我们需要判断是否可以购买。如果可以购买，我们就更新dp数组。具体的做法是，对于每一朵云，我们遍历它的搭配云，如果搭配云已经被购买了，则可以购买当前云，并更新dp数组的值。更新的方式是，如果购买当前云可以获得更大的价值，则更新dp数组的值为购买当前云后可以获得的最大价值。

最后，我们可以通过遍历dp数组找到最大的价值，就是我们可以获得的最大价值。

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

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

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

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

    vector<vector<int>> graph(n);
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        graph[u-1].push_back(v-1);
        graph[v-1].push_back(u-1);
    }

    vector<int> dp(w+1, 0);
    for (int i = 0; i < n; i++) {
        for (int j = w; j >= c[i]; j--) {
            int maxD = d[i];
            for (int k = 0; k < graph[i].size(); k++) {
                int neighbor = graph[i][k];
                if (j >= c[i] + c[neighbor]) {
                    maxD = max(maxD, d[i] + d[neighbor]);
                }
            }
            dp[j] = max(dp[j], dp[j-c[i]] + maxD);
        }
    }

    cout << dp[w] << endl;

    return 0;
}

时间复杂度分析：

• 初始化dp数组需要O(w)的时间复杂度。
• 遍历每一朵云需要O(n)的时间复杂度。
• 对于每一朵云，遍历它的搭配云需要O(m)的时间复杂度。
• 更新dp数组需要O(w)的时间复杂度。 所以总的时间复杂度为O(nmw)。