动态规划 01 背包问题详解与空间优化实战

初始化调整

• dp[0][0] = 0（容量为 0 时价值为 0，且已装满）。
• dp[0][j] = -1（容量大于 0 但无物品，无法装满）。
• 其他 dp[i][0] = 0。

最终答案为 dp[n][V]，若为 -1 则输出 0。

代码实现

#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];
    }

    // 第一问：求最大价值
    // 不需要特殊初始化，全局变量默认为 0
    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[0][0] 外设为 -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 的状态转移方程，计算 dp[i][...] 时只依赖于 dp[i-1][...]。这意味着我们其实不需要保留整个二维表，可以使用滚动数组将空间复杂度从 O(nV) 降至 O(V)。

一维数组推导

将 dp[i][j] 简化为 dp[j]。如果我们直接从左向右遍历，更新 dp[j] 时会用到新的 dp[j - v[i]]，这相当于使用了当前层的数据，导致同一个物品被重复选取（变成了完全背包）。

为了避免这种情况，我们需要从右向左遍历容量 j。这样在计算 dp[j] 时，dp[j - v[i]] 仍然是上一层（即未处理当前物品）的值，保证了每个物品只被使用一次。

优化后的代码

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

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

int main() {
    int n, V;
    cin >> n >> V;

    for (int i = 1; i <= n; ++i) {
        cin >> v[i] >> w[i];
    }

    // 第一问：最大价值
    // 无需初始化，默认 0
    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));
    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;
}

通过这种优化，我们在保持时间复杂度 O(nV) 不变的情况下，显著降低了空间占用，这是处理大规模数据时的关键技巧。