12 背包问题 — 01 背包

GESP C++ 六级：背包问题—01 背包

核心目标：掌握 01 背包的问题模型、二维 DP 推导、一维 DP 空间优化，理解“容量倒序遍历”的根本原因，能区分“最大价值”“恰好装满”“方案数”三种问法的初始化，能独立完成代码实现与真题变体。
01 背包 = 每件物品只能选一次；二维 DP 靠“选或不选”转移，一维 DP 靠“容量倒序”保证每件只用一次；不要求装满全初始化为 0，恰好装满只有 dp[0]=0，其余为 -INF。

一、考纲定位

根据 CCF 官方考纲，GESP 六级明确要求掌握“简单动态规划（一维动态规划、简单背包问题）”。01 背包是背包问题的基础，也是六级 DP 模块的高频考点。

01 背包在六级考试中的考查分布：

考点	重要程度	典型考法
01 背包问题模型	★★★★★	选择题、编程题
二维 DP 转移方程		代码填空、程序阅读
一维 DP 空间优化		代码填空高频
容量倒序遍历的原因		选择题高频
恰好装满的初始化	★★★★☆	编程题、代码填空
方案数统计	★★★★☆	编程题
01 背包与完全背包区别	★★★★★	选择题高频

二、问题模型

有 n 件物品，第 i 件物品重量为 w[i]，价值为 v[i]。背包容量为 W。每件物品最多只能选择一次（选或不选），求背包能装入的最大总价值。

关键约束：每件物品只有两种状态——选（1）或不选（0），因此称为 01 背包。

三、二维 DP 解法

3.1 状态定义

dp[i][j]：考虑前 i 件物品，背包容量为 j 时能获得的最大价值。

3.2 转移方程

对于第 i 件物品：

不选：dp[i][j] = dp[i-1][j]
选（前提 j >= w[i]）：dp[i][j] = dp[i-1][j-w[i]] + v[i]

取两者最大值：

if (j >= w[i])
    dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]] + v[i]);
else
    dp[i][j] = dp[i-1][j];

3.3 边界条件

dp[0][j] = 0，表示没有物品时价值为 0。

3.4 代码模板

int dp[105][10005];

for (int i = 1; i <= n; i++) {
    for (int j = 0; j <= W; j++) {
        dp[i][j] = dp[i-1][j];
        if (j >= w[i]) {
            dp[i][j] = max(dp[i][j], dp[i-1][j-w[i]] + v[i]);
        }
    }
}
cout << dp[n][W] << endl;

复杂度：时间 O(nW)，空间 O(nW)。

四、一维 DP 空间优化（核心）

4.1 优化思路

观察二维转移方程，dp[i][j] 只依赖于 dp[i-1][...]，即只依赖上一行。因此可以去掉第一维，用一维数组滚动更新。

4.2 一维代码模板

int dp[10005] = {0};

for (int i = 1; i <= n; i++) {
    for (int j = W; j >= w[i]; j--) {   // 关键：从大到小！
        dp[j] = max(dp[j], dp[j-w[i]] + v[i]);
    }
}
cout << dp[W] << endl;

复杂度：时间 O(nW)，空间 O(W)。

4.3 为什么容量必须倒序遍历？

这是 01 背包最高频的选择题考点。

倒序 j = W → w[i]：dp[j-w[i]] 尚未被第 i 件物品更新，代表的是“前 i-1 件物品”的状态。因此第 i 件物品只会被选一次。
正序 j = w[i] → W：dp[j-w[i]] 可能已经在本次循环中被第 i 件物品更新过，导致第 i 件物品被重复选择，变成完全背包。

记忆口诀：01 背包倒着走，完全背包正着走。

4.4 二维与一维对比

对比项	二维 DP	一维 DP
状态	`dp[i][j]`	`dp[j]`
空间	O(nW)	O(W)
容量遍历	正序、倒序均可	必须倒序
可回溯方案	✅ 可以	❌ 需要额外记录
适用	需要输出方案	只求最大价值

五、三种常见问法与初始化

5.1 最大价值（不要求装满）

背包不要求恰好装满，求最大价值。

初始化：dp[j] = 0（所有容量初始为 0）。

int dp[10005] = {0};

5.2 恰好装满

要求背包恰好装满，求最大价值。

初始化：dp[0] = 0，其余 dp[j] = -INF。

const int INF = 1e9;
int dp[10005];
dp[0] = 0;
for (int j = 1; j <= W; j++) dp[j] = -INF;

// 转移同上
if (dp[W] < 0) cout << "无解" << endl;
else cout << dp[W] << endl;

原理：只有容量 0 能由“什么都不装”恰好达到；其他容量初始为 -INF，表示不可达。转移时只有可达状态才能更新。

5.3 方案数统计

求装满容量 W 的方案数。

初始化：dp[0] = 1，其余 dp[j] = 0。

int dp[10005] = {0};
dp[0] = 1;

for (int i = 1; i <= n; i++) {
    for (int j = W; j >= w[i]; j--) {   // 仍然倒序
        dp[j] += dp[j-w[i]];
    }
}
cout << dp[W] << endl;

六、输出方案（了解）

如果需要输出具体选了哪些物品，需要保留二维 DP 或额外记录选择。

回溯法：

int i = n, j = W;
while (i > 0 && j > 0) {
    if (dp[i][j] != dp[i-1][j]) {   // 选了第 i 件
        cout << i << " ";
        j -= w[i];
    }
    i--;
}

一维 DP 丢失了历史信息，无法直接回溯，需要二维数组或记录 choice。

七、01 背包与完全背包的区别

对比项	01 背包	完全背包
物品使用次数	每件最多 1 次	每件无限次
二维转移	`dp[i-1][j-w] + v`	`dp[i][j-w] + v`
一维容量遍历	倒序 `W → w[i]`	正序 `w[i] → W`
典型题	采药、装箱	零钱兑换、无限背包

选择题高频：把 01 背包的容量循环改成正序，会变成什么？答案：完全背包。

八、典型例题与代码

例题：采药（01 背包模板）

题目：有 n 株草药，每株有采集时间 t[i] 和价值 v[i]，总时间 T。每株草药只能采一次，求最大总价值。

#include <iostream>
using namespace std;

int main() {
    int T, n;
    cin >> T >> n;
    int t[105], v[105];
    for (int i = 1; i <= n; i++) {
        cin >> t[i] >> v[i];
    }

    int dp[1005] = {0};
    for (int i = 1; i <= n; i++) {
        for (int j = T; j >= t[i]; j--) {
            dp[j] = max(dp[j], dp[j-t[i]] + v[i]);
        }
    }
    cout << dp[T] << endl;
    return 0;
}

例题：装箱问题（求剩余空间最小）

题目：有一个箱子容量为 V，有 n 个物品，每个物品有体积。求箱子剩余空间的最小值。

转化：把体积同时看作重量和价值，求能装入的最大体积，答案 = V - dp[V]。

int dp[20005] = {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]] + v[i]);
    }
}
cout << V - dp[V] << endl;

九、易错点汇总

一维 DP 容量正序遍历：导致物品被重复选择，变成完全背包。
物品循环与容量循环写反：01 背包必须物品在外层，容量在内层。
容量循环边界写错：j >= w[i]，不能写成 j > w[i]。
恰好装满忘记初始化：dp[0]=0，其余 -INF，否则无解会被误判为 0。
方案数统计忘记倒序：方案数也要倒序，否则同一物品被重复计数。
dp 数组未初始化：全局数组默认 0，局部数组需要手动初始化。
价值/容量溢出：大数用 long long。
W 过大导致数组越界：数组大小要开到 W+1。
输出方案时一维 DP 无法回溯：需要二维 DP 或记录选择。
“恰好装满”与“不超过容量”混淆：初始化不同，结果不同。

十、速查表

需求	写法	关键注意
二维 01 背包	`dp[i][j]=max(dp[i-1][j], dp[i-1][j-w]+v)`	依赖上一行
一维 01 背包	`for(j=W; j>=w[i]; j--) dp[j]=max(dp[j], dp[j-w]+v)`	倒序
最大价值	`dp[j]=0`	不要求装满
恰好装满	`dp[0]=0`，其余 `-INF`	最后判 `dp[W]<0`
方案数	`dp[0]=1`，`dp[j]+=dp[j-w]`	倒序
剩余空间最小	体积当价值，答案 `V-dp[V]`	转化
01 vs 完全	01 倒序，完全正序	选择题高频
时间复杂度	O(nW)	空间 O(W)

十一、总结

01 背包是 GESP 六级动态规划模块的核心模型。

01 背包每件物品只能选一次，选或不选。
二维 DP：dp[i][j] = max(dp[i-1][j], dp[i-1][j-w]+v)。
一维 DP 去掉第一维，空间从 O(nW) 降为 O(W)。
一维 01 背包容量必须从大到小遍历。
正序遍历会变成完全背包，这是选择题最高频考点。
不要求装满：dp 全初始化为 0。
恰好装满：dp[0]=0，其余 -INF。
方案数统计：dp[0]=1，倒序累加。
输出方案需要二维 DP 或额外记录。
多练“采药”“装箱问题”“恰好装满”“方案数”四类题。

复习建议：先把二维 01 背包的转移方程写熟，再动手改成一维并理解倒序的原因；然后重点练习“恰好装满”和“方案数”两种初始化；最后用“采药”和“装箱问题”两道经典题巩固。考试中先判断题目是最大价值、恰好装满还是方案数，再确定初始化方式，最后检查容量循环方向。