这道题可以使用动态规划来解决。

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

然后,我们可以使用一个循环来遍历所有的云朵,对于每朵云,我们需要考虑两种情况:

  1. 不购买这朵云,那么dp[i][j] = dp[i-1][j],即不购买这朵云的情况下的最大价值与前i-1朵云的最大价值相同。
  2. 购买这朵云,那么我们需要考虑是否需要购买该云的搭配云。如果需要购买搭配云,那么我们需要判断购买搭配云的总价值是否小于等于j的情况下的最大价值,如果小于等于j,那么我们可以更新dp[i][j] = max(dp[i][j], dp[i-1][j-c]+d),其中c为该云的价格,d为该云的价值。如果不需要购买搭配云,那么我们可以更新dp[i][j] = max(dp[i][j], dp[i-1][j-c]+d)。

最后,我们可以输出dp[n][w],即在前n朵云中,花费w元钱能够获得的最大价值。

C++代码如下:

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

int main() {
    int n, m, w;
    cin >> n >> m >> w;
    
    vector<int> c(n+1);
    vector<int> d(n+1);
    for (int i = 1; i <= n; i++) {
        cin >> c[i] >> d[i];
    }
    
    vector<vector<bool>> buy(n+1, vector<bool>(n+1, false));
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        buy[u][v] = true;
        buy[v][u] = true;
    }
    
    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]);
                for (int k = 1; k <= n; k++) {
                    if (buy[i][k] && j >= c[i] + c[k]) {
                        dp[i][j] = max(dp[i][j], dp[i-1][j-c[i]-c[k]] + d[i] + d[k]);
                    }
                }
            }
        }
    }
    
    cout << dp[n][w] << endl;
    
    return 0;
}

复杂度分析: 时间复杂度:O(n^2 * w) 空间复杂度:O(n * w)

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

原文地址: https://www.cveoy.top/t/topic/pawo 著作权归作者所有。请勿转载和采集!

免费AI点我,无需注册和登录