基础背包 DP：0/1 背包与完全背包

适合谁、学完能做什么

适合已经学过数组、循环和基础递推，准备学习动态规划的学生。学完后，你应该能够：

• 把“容量有限、选择物品、最大化价值”抽象成状态。
• 写出二维0/1背包状态转移。
• 将二维状态压缩成一维数组。
• 正确理解0/1背包为什么必须倒序循环。
• 说明完全背包为什么通常正序循环。
• 根据题目判断每件物品能否重复使用。

前置知识与网站关联

必须掌握一维数组、循环、max、基础递推，以及“从前一个状态推出当前状态”的思想。

对应地图节点：dp.1e8642742a（背包DP）、dp.151f7eb32d（01背包）、dp.232f98a5d2（完全背包）、search.memo（记忆化搜索补充）。

配套专题：CSP-J|动态规划|背包DP|。

问题引入

有容量为 W 的背包和 n 件物品，第 i 件物品重量为 w[i]，价值为 v[i]，每件最多选择一次，求最大价值。

例如容量为7：

选A和B，重量为7，价值为9。枚举所有组合可以解决小数据，但大数据中会出现大量重复子问题。

核心概念：状态和转移

定义：

dp[i][j] = 只考虑前 i 件物品，容量不超过 j 时的最大价值

处理第 i 件物品时有两种选择：

不选：dp[i-1][j]
选取：dp[i-1][j-w[i]] + v[i]

所以当 w[i] <= j 时：

dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]] + v[i])

一维压缩后：

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]);

容量倒序保证 dp[j-w[i]] 仍然是处理当前物品前的旧状态，所以当前物品最多使用一次。

0/1背包与完全背包比较

完全背包只需把容量循环改成正序：

for (int i = 1; i <= n; ++i)
    for (int j = w[i]; j <= W; ++j)
        dp[j] = max(dp[j], dp[j-w[i]] + v[i]);

正序时，dp[j-w[i]] 可能已经使用当前物品更新过，所以允许继续使用当前物品。

算法步骤与正确性

1. 读入物品数量 n 和容量 W。
2. 初始化 dp[0..W] = 0。
3. 依次处理每件物品。
4. 对容量从 W 倒序枚举到物品重量。
5. 比较“不选”和“选择”两种结果。
6. 输出 dp[W]。

每个合法方案都可以分成“不选当前物品”和“选当前物品”两类。倒序确保第二类从上一层状态转移，不会重复使用当前物品；两类取最大值就是最优状态。初始状态表示没有物品时价值为0，因此处理完全部物品后得到正确答案。

完整 C++ 示例

语言：C++17。输入第一行 n W，接下来每行输入重量 w 和价值 v；每件物品最多选择一次。

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

struct Item {
    int weight;
    int value;
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, capacity;
    cin >> n >> capacity;
    vector<Item> items(n + 1);
    for (int i = 1; i <= n; ++i)
        cin >> items[i].weight >> items[i].value;

    vector<int> dp(capacity + 1, 0);
    for (int i = 1; i <= n; ++i) {
        for (int j = capacity; j >= items[i].weight; --j) {
            dp[j] = max(dp[j], dp[j-items[i].weight] + items[i].value);
        }
    }

    cout << dp[capacity] << '\n';
    return 0;
}

如果改成完全背包，只需把内层循环改为：

for (int j = items[i].weight; j <= capacity; ++j)
    dp[j] = max(dp[j], dp[j-items[i].weight] + items[i].value);

复杂度与适用范围

设物品数为 n，容量为 W：

• 时间复杂度：O(nW)。
• 一维空间复杂度：O(W)。
• 二维空间复杂度：O(nW)。

适合容量不太大的问题。如果容量很大，O(nW)可能不可行，需要考虑按价值DP、分治、单调队列优化或其他建模。若题目要求“恰好装满”，不可达状态不能全部初始化为0，应使用负无穷并单独设置 dp[0]=0。

易错点

1. 0/1背包使用正序：会把同一件物品重复使用。纠正为容量倒序。
2. 完全背包使用倒序：会把每种物品限制成最多一次。纠正为容量正序。
3. 混淆“容量不超过”和“恰好装满”：两种状态的初始化不同。
4. 忽略使用次数：每件一次、每种无限次、每种有数量上限，转移方式不同。
5. 忘记判断容量：只有 j >= weight 才能访问 dp[j-weight]。

配套练习

以下题目来自本地 CSP-J|动态规划|背包DP| 专题，题名、链接和难度已核对。当前内容工作室没有这些题的已发布题解，均只提供原题入口。

基础：0/1背包

1. P1060：[NOIP 2006 普及组] 开心的金明（普及-）：经典0/1背包，适合第一次完成状态转移。
2. P2871：[USACO07DEC] Charm Bracelet S（普及-）：适合专门练习一维数组和倒序循环。
3. P2925：[USACO08DEC] Hay For Sale S（普及-）：巩固每件物品只能使用一次的模型。

变式：完全背包

1. P2722：[USACO3.1] 总分 Score Inflation（普及-）：适合观察0/1背包改成完全背包后的循环变化。
2. P2918：[USACO08NOV] Buying Hay S（普及）：练习完全背包和目标容量状态设计。

自查与小结

完成本篇后，应能回答：dp[i][j]表示什么？0/1背包为什么倒序？完全背包为什么正序？恰好装满如何初始化？容量很大时为什么不能直接使用O(nW)？

能够独立写出0/1背包、解释循环方向，并把代码改成完全背包，就可以继续学习多重背包、分组背包和背包优化。