如何免费做网站推广/站长工具seo客户端

目录

 一、问题描述​

 二、解题思路

 三、完整代码

二维dp

使用滚动数组

---

 一、问题描述

 二、解题思路

一个变种的01背包问题：

1. 不选该物品：获得固定收益 e

2. 选择方案1：消耗体积 a，获得价值 b

3. 选择方案2：消耗体积 c，获得价值 d

目标是在背包容量 m 的限制下，最大化总收益。

 三、完整代码

二维dp

#include <bits/stdc++.h>
using namespace std;
using ll = long long;const int N = 1010;
ll dp[N][N]; // dp[i][j] 表示前 i 个物品，容量为 j 时的最大价值
ll n, m, a, b, c, d, e;int main() {cin >> n >> m; // 输入物品数量 n 和背包容量 mfor (int i = 1; i <= n; i++) {  // 遍历每个物品cin >> a >> b >> c >> d >> e;for (int j = 0; j <= m; j++) { // 不选当前物品，继承上一个状态dp[i][j] = dp[i - 1][j] + e;  // 选方案1（需要容量 >= a）if (j >= a) dp[i][j] = max(dp[i][j], dp[i - 1][j - a] + b);// 选方案2（需要容量 >= c）if (j >= c) dp[i][j] = max(dp[i][j], dp[i - 1][j - c] + d);}}cout << dp[n][m] << '\n'; // 输出最大价值return 0;
}

使用滚动数组

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 1010;
ll dp[N], n, m, a, b, c, d, e;
int main(){cin >> n >> m;  // 输入物品数量n和背包容量mwhile(n -- ){   // 遍历每个物品cin >> a >> b >> c >> d >> e;  // 输入物品参数for(int i = m; i >= 0; -- i) { // 逆向遍历背包容量// 处理三种决策if(i >= a) dp[i] = max(dp[i] + e, dp[i - a] + b); // 方案1 vs 不选if(i >= c) dp[i] = max(dp[i], dp[i - c] + d);     // 方案2 vs 当前最优if(i < a) dp[i] = dp[i] + e;                     // 无法选方案1，只能不选}}cout << dp[m] << '\n';  // 输出结果return 0;
}

---

 关键逻辑说明

1. 逆向遍历背包容量
   使用 for(int i = m; i >= 0; -- i) 确保每个物品只被处理一次（类似01背包优化）。

2. 三种决策的优先级

方案1优先：先尝试选择体积 a 的方案，更新 dp[i]。

方案2次优先：再尝试选择体积 c 的方案，与当前最优值比较。

强制不选：当 i < a 时，强制加上不选收益 e。