01 背包问题详解与空间优化实战

01 背包问题详解与空间优化实战

动态规划是算法竞赛和面试中的常客，而背包问题则是 DP 家族中最经典的一类。很多人听到背包就头疼，其实只要理清状态定义和转移逻辑，核心思想并不复杂。本文将深入剖析 01 背包的两种常见变体，并讲解如何通过滚动数组进行空间优化。

问题描述

给定一个容量为 V 的背包和 n 个物品，每个物品有体积 vi 和价值 wi。

1. 求最大价值：在不超过背包容量的前提下，能装入物品的最大总价值是多少？
2. 恰好装满：若要求背包必须恰好装满，此时的最大价值是多少？若无解则输出 0。

输入格式通常为第一行两个整数 n 和 V，随后 n 行每行给出 vi 和 wi。

二维 DP 解法

状态定义

我们定义 dp[i][j] 表示从前 i 个物品中选择，且总体积不超过 j 时能获得的最大价值。

这里需要特别注意维度含义：第一个维度代表物品索引，第二个维度代表当前背包的剩余容量限制。

状态转移

对于第 i 个物品，我们有两种选择：

1. 不选：价值保持不变，即 dp[i][j] = dp[i - 1][j]
2. 选：前提是当前容量足够（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;

     ;
}