C++ 母亲节送云朵：动态规划解决搭配购买问题

明天就是母亲节了，电脑组的小朋友们在忙碌的课业之余挖空心思想着该送什么礼物来表达自己的心意呢？听说在某个网站上有卖云朵的，小朋友们决定一同前往去看看这种神奇的商品，这个店里有n朵云，云朵已经被老板编号为1,2,3,...,n，并且每朵云都有一个价值，但是商店的老板是个很奇怪的人，他会告诉你一些云朵要搭配起来买才卖，也就是说买一朵云则与这朵云有搭配的云都要买，电脑组的你觉得这礼物实在是太新奇了，但是你的钱是有限的，所以你肯定是想用现有的钱买到尽量多价值的云。

输入格式： 第1行输入三个整数,n,m,w表示有 n 朵云，m 个搭配和你现有的钱的数目w。 第2行输入第2行至n+1 行，每行有两个整数，c，d，表示第i朵云的价钱和价值。 第n+2至n+1+m 行 ，每行有两个整数u,v。表示买第u朵云就必须买第v朵云。同理，如果买第v就必须买第u朵。 输出格式：一行，表示可以获得的最大价值。

解题思路： 这是一个典型的背包问题，可以使用动态规划来解决。创建一个二维数组dp，dp[i][j]表示在前i个云朵中，花费j元钱能够获得的最大价值。初始化dp数组为0。

然后，遍历每个云朵，对于第i个云朵，我们有两种选择：买或不买。 如果选择不买，那么dp[i][j] = dp[i-1][j]，表示在前i-1个云朵中花费j元钱所能获得的最大价值。 如果选择买，那么dp[i][j] = dp[i-1][j-c] + d，表示在前i-1个云朵中花费j-c元钱所能获得的最大价值再加上第i个云朵的价值d。

综上，动态规划转移方程为：dp[i][j] = max(dp[i-1][j], dp[i-1][j-c] + d)。

最后，遍历完所有云朵后，dp[n][w]就是最终的答案，表示在前n个云朵中花费w元钱所能获得的最大价值。

C++代码实现如下：

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

int main() {
    int n, m, w;
    cin >> n >> m >> w;
    
    vector<int> c(n+1), d(n+1);
    for (int i = 1; i <= n; i++) {
        cin >> c[i] >> d[i];
    }
    
    vector<vector<int>> dp(n+1, vector<int>(w+1, 0));
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j <= w; j++) {
            dp[i][j] = dp[i-1][j];
            if (j >= c[i]) {
                dp[i][j] = max(dp[i][j], dp[i-1][j-c[i]] + d[i]);
            }
        }
    }
    
    cout << dp[n][w] << endl;
    
    return 0;
}