01 背包问题详解与空间优化实战
动态规划是算法竞赛和面试中的常客,而背包问题则是 DP 家族中最经典的一类。很多人听到背包就头疼,其实只要理清状态定义和转移逻辑,核心思想并不复杂。本文将深入剖析 01 背包的两种常见变体,并讲解如何通过滚动数组进行空间优化。
问题描述
给定一个容量为 V 的背包和 n 个物品,每个物品有体积 vi 和价值 wi。
- 求最大价值:在不超过背包容量的前提下,能装入物品的最大总价值是多少?
- 恰好装满:若要求背包必须恰好装满,此时的最大价值是多少?若无解则输出 0。
输入格式通常为第一行两个整数 n 和 V,随后 n 行每行给出 vi 和 wi。
二维 DP 解法
状态定义
我们定义 dp[i][j] 表示从前 i 个物品中选择,且总体积不超过 j 时能获得的最大价值。
这里需要特别注意维度含义:第一个维度代表物品索引,第二个维度代表当前背包的剩余容量限制。
状态转移
对于第 i 个物品,我们有两种选择:
- 不选:价值保持不变,即
dp[i][j] = dp[i - 1][j] - 选:前提是当前容量足够(
j >= vi),价值为dp[i - 1][j - vi] + wi
取两者最大值即可:
dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - v[i]] + w[i]);
初始化与遍历
- 初始化:通常全部初始化为 0。因为
dp[0][j]表示没有物品可选,价值自然为 0;dp[i][0]表示背包容量为 0,也无法装东西。 - 遍历顺序:由于计算
dp[i]依赖dp[i-1],所以外层循环遍历物品i,内层循环遍历容量j,顺序均为从小到大。
恰好装满的处理
当题目要求'恰好装满'时,状态定义变为 dp[i][j] 表示前 i 个物品总体积正好等于 j 时的最大价值。
关键区别在于初始化:
dp[0][0] = 0(容量为 0 时价值为 0)dp[0][j] = -1(容量不为 0 但无物品时无法装满,标记为不可达)
在转移方程中,如果 dp[i - 1][j - v[i]] 为 -1,说明之前的状态无法构成该体积,此时不能选择当前物品来更新状态。
代码实现(二维)
#include <iostream>
std;
N = ;
n, V, v[N], w[N];
dp[N][N];
{
cin >> n >> V;
( i = ; i <= n; ++i) {
cin >> v[i] >> w[i];
}
( i = ; i <= n; ++i) {
( j = ; j <= V; ++j) {
dp[i][j] = dp[i - ][j];
(j >= v[i]) {
dp[i][j] = (dp[i][j], dp[i - ][j - v[i]] + w[i]);
}
}
}
cout << dp[n][V] << endl;
(dp, , (dp));
( j = ; j <= V; ++j) dp[][j] = ;
( i = ; i <= n; ++i) {
( j = ; j <= V; ++j) {
dp[i][j] = dp[i - ][j];
(j >= v[i] && dp[i - ][j - v[i]] != ) {
dp[i][j] = (dp[i][j], dp[i - ][j - v[i]] + w[i]);
}
}
}
cout << (dp[n][V] == ? : dp[n][V]) << endl;
;
}


