目录
一、问题描述
二、解题思路
三、完整代码
二维dp
使用滚动数组
一、问题描述
二、解题思路
一个变种的01背包问题:
不选该物品:获得固定收益
e
选择方案1:消耗体积
a
,获得价值b
选择方案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;
}
关键逻辑说明
-
逆向遍历背包容量
使用for(int i = m; i >= 0; -- i)
确保每个物品只被处理一次(类似01背包优化)。 -
三种决策的优先级
方案1优先:先尝试选择体积
a
的方案,更新dp[i]
。方案2次优先:再尝试选择体积
c
的方案,与当前最优值比较。强制不选:当
i < a
时,强制加上不选收益e
。