五大经典背包问题的终极归纳，涵盖核心思想、算法实现、适用场景及关键对比

1. 01背包问题

特点：每件物品最多选一次
状态定义：f[i][j] 表示前i件物品在容量j下的最大价值
状态转移：

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

优化：
- 空间优化到一维：f[j] = max(f[j], f[j-v[i]] + w[i])
- 逆序枚举容量（防止重复选择）

适用场景：
- 物品唯一性选择（选/不选）
- 典型问题：分割等和子集、目标和

2. 完全背包问题

特点：物品无限次选择
状态转移：

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

优化：
- 一维数组 + 正序枚举容量（允许重复选择）
- 数学优化：转换为体积的gcd问题（特定场景）

适用场景：
- 物品可无限使用
- 典型问题：零钱兑换、完全平方数

3. 多重背包问题（基础版）

特点：物品有限次数选择（s[i]次）
状态转移：

for(int k=0; k<=s[i] && k*v[i]<=j; k++)
    f[i][j] = max(f[i][j], f[i-1][j-k*v[i]] + k*w[i])

局限：
- 三重循环，O(N·V·S)复杂度，仅适合小数据量（S≤100）

4. 多重背包问题（二进制优化版）

核心思想：将s[i]拆分为二进制组合（1,2,4,…,剩余）
优化步骤：
1. 将每个物品拆分为log₂s[i]个新物品
2. 转化为01背包问题
复杂度：O(N·V·logS)
适用场景：
- 物品种类多且数量大（如S≤2000）
- 典型问题：大容量多重背包

5. 分组背包问题

特点：每组物品最多选一个
状态转移：

for(int k=0; k<s[i]; k++)  // 遍历组内物品
    if(v[i][k] <= j)
        f[j] = max(f[j], f[j-v[i][k]] + w[i][k])

关键点：
- 容量需逆序枚举（同01背包）
- 组内物品循环在容量循环内部

适用场景：
- 具有互斥选择的物品组
- 典型问题：课程选修（多选一）

终极对比表

核心技巧总结

1. 状态设计：
2. 绝大多数背包问题使用f[j]表示容量为j时的最大价值

3. 若需记录选择方案，可增加辅助数组g[][]

4. 枚举顺序：

5. 逆序（01背包、分组背包）：防止重复选择
6. 正序（完全背包）：允许重复选择

7. 组内全枚举（分组背包）：确保每组只选一个

8. 优化思路：

9. 空间优化：01/完全/分组背包均可压缩到一维
10. 多重背包：二进制拆分是通用优化手段

11. 贪心优化：当物品价值与体积成比例时，可贪心选择

12. 边界处理：

13. 初始化f[0]=0，其余为-INF（求恰好装满时的最大值）
14. 初始化全为0（普通最大价值问题）

代码模板选择指南

• 小数据量（N,V≤100）：直接使用基础多重背包
• 大数据量（N,V≤1000）：优先二进制优化
• 存在特殊约束：
• 需要恰好装满 → 修改初始化
• 求方案数 → 将max改为+=
• 求具体方案 → 记录状态转移路径