C++ 母亲节礼物：云朵搭配背包问题

这是一个背包问题，只是在选择物品时需要考虑搭配条件。

首先定义一个二维数组dp，其中dp[i][j] 表示前i朵云中选择搭配条件满足的云朵总价值不超过j时能够获得的最大价值。

然后对于每一朵云，判断其是否满足搭配条件，如果满足条件，则将其价值加入到dp数组中。

最后输出dp数组中最后一行的最大值即为所求的结果。

代码实现如下：

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

int main() {
    int n, m, w;
    cin >> n >> m >> w;
    vector<int> price(n+1); // 云朵的价钱
    vector<int> value(n+1); // 云朵的价值
    vector<vector<int>> match(n+1, vector<int>(n+1)); // 云朵之间的搭配条件
    vector<vector<int>> dp(n+1, vector<int>(w+1, 0)); // 动态规划数组

    for (int i = 1; i <= n; i++) {
        cin >> price[i] >> value[i];
    }

    for (int i = 1; i <= m; i++) {
        int u, v;
        cin >> u >> v;
        match[u][v] = 1;
        match[v][u] = 1;
    }

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= w; j++) {
            if (j >= price[i]) {
                dp[i][j] = max(dp[i-1][j], dp[i-1][j-price[i]] + value[i]);
            } else {
                dp[i][j] = dp[i-1][j];
            }
            // 判断搭配条件
            for (int k = 1; k < i; k++) {
                if (match[i][k] && dp[i][j] < dp[k][j]) {
                    dp[i][j] = dp[k][j];
                }
            }
        }
    }

    cout << dp[n][w] << endl;

    return 0;
}