动态规划：01 背包详解与空间优化

初始化修改

dp[0][0] 初始化为 0，其余 dp[0][j] 初始化为 -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;

    // 填入题目给出的物品体积和价值的数组
    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));
    // 第一行除了第一个元素之外其它元素初始化为 -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][j] 依赖 dp[i - 1][j] 和 dp[i - 1][j - v[i]]，即上一行的数据。因此可以压缩为一维数组 dp[j]。

滚动数组原理

使用一维数组时，若从左往右遍历，更新 dp[j] 时会用到已更新的 dp[j - v[i]]，这会导致当前物品被重复选取（类似完全背包）。因此，必须从右往左遍历，确保使用的是上一轮的数据。

优化操作总结

1. 删除横坐标 i，只保留一维数组 dp[j]。
2. 修改 j 的遍历顺序为从大到小（V 到 v[i]）。
3. 时间上，只需遍历到 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));
    // 初始化除 dp[0] 外为 -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;
}