01背包用一维数组实现的核心是倒序遍历容量j以避免重复选物，空间复杂度从o(n×w)降至o(w)；需注意下标对齐、初始化及溢出处理。
用数组实现 01 背包，核心是用 dp[j] 表示容量为 j 的背包能装下的最大价值。关键不在“能不能写出来”，而在“怎么让数组既正确又省空间”。下面从基础逻辑到实战优化分步说明。
一、二维数组打底：理解状态含义
定义 dp[i][j] 为考虑前 i 个物品、背包容量为 j 时的最大价值。状态转移由两个选择决定：
- 不选第 i 个物品：价值继承自 dp[i−1][j]
- 选第 i 个物品（前提是 j ≥ weight[i]）：价值为 dp[i−1][j − weight[i]] + value[i]
取两者较大值：dp[i][j] = max(dp[i−1][j], dp[i−1][j − weight[i]] + value[i])。初始化时，所有 dp[0][j] = 0（没物品可选），dp[i][0] = 0（容量为 0）。这种写法逻辑清晰，但空间复杂度为 O(n×W)，易超内存。
二、一维数组优化：滚动覆盖的关键细节
观察发现，每次更新 dp[i][j] 只依赖上一行（i−1）的数据，因此可压缩为一维 dp[j]。但必须注意遍历顺序：
- 内层循环容量 j 必须从大到小（即 j = W 到 weight[i]）
- 若从小到大遍历，会导致同一个物品被重复使用（退化为完全背包）
- 每次执行 dp[j] = max(dp[j], dp[j − weight[i]] + value[i])，其中右侧的 dp[j − weight[i]] 还是上一轮（i−1）的值
这样空间从 O(n×W) 降到 O(W)，且代码更简洁。
三、实战中变量存储的常见优化点
真实编码时，几个容易忽略但影响稳定性的细节：
- 数组大小留余量：定义 dp[W+1]，下标 0～W 对应容量 0 到 W，避免越界
- weight/value 数组下标对齐：建议从索引 1 开始存（如 w[1], w[2]…），与 dp 循环 i=1→n 保持一致，减少边界错位
- 初始化统一设为 0：对于“至多装多少价值”问题，初始全 0 即可；若要求“恰好装满”，则除 dp[0]=0 外其余设为负无穷（如 -0x3f3f3f3f），防止非法状态参与转移
- 用 int 替代 long 时注意溢出：当价值总和可能超 2×10⁹，改用 long 或加溢出判断
四、一个精简可运行的 C++ 示例
假设输入格式为：第一行 V（背包容量）、n（物品数），随后 n 行每行 weight value：
int V, n;
cin >> V >> n;
vector<int> w(n+1), v(n+1);
for (int i = 1; i > w[i] >> v[i];
<p>vector<int> dp(V+1, 0);
for (int i = 1; i = w[i]; j--) {
dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
}
}
cout </int></p>
<p>这段代码无冗余变量、下标清晰、空间紧凑，适合嵌入竞赛或工程模块中直接复用。</p></int>
