动态规划 01 背包问题详解、模板与空间优化

返回值

返回 dp[n][V]。

第二问解题思路

针对'恰好装满'的要求，需修改状态表示和初始化细节。

状态表示修改

dp[i][j] 表示从前 i 个物品中选择，并且物品总体积正好等于背包空间 j，此时这些选法中能装入背包的最大物品价值。

状态转移方程细节修改

判断 dp[i - 1][j - v[i]] 是否有效。设定 dp[i][j] == -1 表示无法凑到背包空间 j。

初始化修改

第一行除了第一个元素之外其它元素初始化为 -1，表示无法装满。

代码（二维 DP）

#include <iostream>
#include <cstring>
using namespace std;

const int N = 1010;
int n, V, v[N], w[N];
int dp[N][N];

int main() {
    int n, V; 
    cin >> n >> V;
    // 填入题目给出的物品体积和价值的数组 -- 从下标为 1 开始
    for(int i = 1; i <= n; ++i) cin >> v[i] >> w[i];

    // 解决第一问：求这个背包至多能装多大价值的物品
    // 不需要初始化
    for(int i = 1; i <= n; ++i) {
        for(int j = 1; j <= V; ++j) {
            dp[i][j] = dp[i - 1][j];
            if(j >= v[i]) dp[i][j] = max(dp[i][j], dp[i - 1][j - v[i]] + w[i]);
        }
    }
    cout << dp[n][V] << endl;

    // 解决第二问：若背包恰好装满，求至多能装多大价值的物品
    memset(dp, 0, sizeof(dp));
    // 先清空 dp 表
    // 第一行除了第一个元素之外其它元素初始化为 -1
    for(int i = 1; i <= V; ++i) dp[0][i] = -1;
    for(int i = 1; i <= n; ++i) {
        for(int j = 1; j <= V; ++j) {
            dp[i][j] = dp[i - 1][j];
            if(j >= v[i] && dp[i - 1][j - v[i]] != -1) dp[i][j] = max(dp[i][j], dp[i - 1][j - v[i]] + w[i]);
        }
    }
    cout << (dp[n][V] == -1 ? 0 : dp[n][V]) << endl;
    return 0;
}

空间优化

背包问题通常利用「滚动数组」做空间优化。我们发现每次遍历只用到 dp[i - 1][j] 和 dp[i - 1][j - v[i]]，即上一行的数据。因此可以将二维数组压缩为一维数组。

关键在于遍历顺序。如果使用一维数组 dp[j]，当计算 dp[j] 时需要用到 dp[j - v[i]]。如果从左往右遍历，dp[j - v[i]] 可能已经被当前轮次更新过，导致重复使用同一物品。因此必须从右往左遍历容量 j。

优化操作总结：

1. 删掉所有的横坐标（维度 i）。
2. 修改 j 的遍历顺序（从 V 到 v[i] 逆序）。

空间优化后，空间复杂度从 O(nV) 降至 O(V)。

优化后的代码（一维 DP）

#include <iostream>
#include <cstring>
using namespace std;

const int N = 1010;
int n, V, v[N], w[N];
int dp[N]; // 只需要一维 dp 数组

int main() {
    int n, V; 
    cin >> n >> V;
    // 填入题目给出的物品体积和价值的数组 -- 从下标为 1 开始
    for(int i = 1; i <= n; ++i) cin >> v[i] >> w[i];

    // 解决第一问：求这个背包至多能装多大价值的物品
    // 不需要初始化
    for(int i = 1; i <= n; ++i) {
        for(int j = V; j >= v[i]; --j) {
            dp[j] = max(dp[j], dp[j - v[i]] + w[i]);
        }
    }
    cout << dp[V] << endl;

    // 解决第二问：若背包恰好装满，求至多能装多大价值的物品
    memset(dp, 0, sizeof(dp));
    // 先清空 dp 表
    // 第一行除了第一个元素之外其它元素初始化为 -1
    for(int j = 1; j <= V; ++j) dp[j] = -1;
    for(int i = 1; i <= n; ++i) {
        for(int j = V; j >= v[i]; --j) {
            if(dp[j - v[i]] != -1) dp[j] = max(dp[j], dp[j - v[i]] + w[i]);
        }
    }
    cout << (dp[V] == -1 ? 0 : dp[V]) << endl;
    return 0;
}