C++ 动态规划解决云朵购买问题
这道题可以使用动态规划来解决。
首先,我们可以定义一个二维数组dp,dp[i][j]表示在前i朵云中,花费j元钱能够获得的最大价值。
然后,我们可以使用一个循环来遍历所有的云朵,对于每朵云,我们需要考虑两种情况:
- 不购买这朵云,那么dp[i][j] = dp[i-1][j],即不购买这朵云的情况下的最大价值与前i-1朵云的最大价值相同。
- 购买这朵云,那么我们需要考虑是否需要购买该云的搭配云。如果需要购买搭配云,那么我们需要判断购买搭配云的总价值是否小于等于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)
原文地址: https://www.cveoy.top/t/topic/pawo 著作权归作者所有。请勿转载和采集!