C++ 母亲节礼物：云朵购物问题 - 动态规划解法

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

首先定义一个二维数组dp，dp[i][j]表示在前i朵云中花费j元钱所能获得的最大价值。

初始化dp数组为0。

然后遍历每一朵云，对于第i朵云，有两种情况：

1. 不购买第i朵云，即dp[i][j] = dp[i-1][j]
2. 购买第i朵云，需要考虑是否需要搭配购买其他云。假设第i朵云的价格为c，价值为d，需要搭配购买的云的编号为u，那么dp[i][j] = max(dp[i][j], dp[i-1][j-c] + d)，其中j-c表示购买第i朵云后剩余的钱。

最后，输出dp[n][w]即可得到最大价值。

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

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

int main() {
    int n, m, w;
    cin >> n >> m >> w;
    
    vector<int> prices(n+1);
    vector<int> values(n+1);
    vector<vector<int>> dp(n+1, vector<int>(w+1, 0));
    
    for (int i = 1; i <= n; i++) {
        cin >> prices[i] >> values[i];
    }
    
    for (int i = 1; i <= m; i++) {
        int u, v;
        cin >> u >> v;
        // 如果购买第u朵云，则必须购买第v朵云，价值相加
        values[u] += values[v];
        prices[u] += prices[v];
    }
    
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j <= w; j++) {
            if (prices[i] <= j) {
                dp[i][j] = max(dp[i-1][j], dp[i-1][j-prices[i]] + values[i]);
            } else {
                dp[i][j] = dp[i-1][j];
            }
        }
    }
    
    cout << dp[n][w] << endl;
    
    return 0;
}

时间复杂度分析：由于要遍历每一朵云和每一种金额，所以时间复杂度为O(nw)。

空间复杂度分析：需要一个二维数组dp来存储中间结果，所以空间复杂度为O(nw)。