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

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

if(v[i][k] <= j)

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

关键点：

- 容量需逆序枚举（同01背包）

- 组内物品循环在容量循环内部

适用场景：

- 具有互斥选择的物品组

- 典型问题：课程选修（多选一）

终极对比表

问题类型

选择限制

核心转移方程

空间优化要点

时间复杂度

经典问题

01背包

选0/1次

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

逆序枚举j

O(NV)

分割等和子集

完全背包

无限次

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

正序枚举j

O(NV)

零钱兑换

多重背包I

最多s次

枚举k次选择

二维数组

O(NVS)

小额商品采购

多重背包II

最多s次

二进制拆分+01背包

逆序枚举j

O(NVlogS)

大规模物资装载

分组背包

每组选0/1个

组内物品循环+01背包逻辑

逆序枚举j

O(NVS)

课程组合优化

核心技巧总结

状态设计：

绝大多数背包问题使用f[j]表示容量为j时的最大价值

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

枚举顺序：

逆序（01背包、分组背包）：防止重复选择

正序（完全背包）：允许重复选择

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

优化思路：

空间优化：01/完全/分组背包均可压缩到一维

多重背包：二进制拆分是通用优化手段

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

边界处理：

初始化f[0]=0，其余为-INF（求恰好装满时的最大值）

初始化全为0（普通最大价值问题）

代码模板选择指南

小数据量（N,V≤100）：直接使用基础多重背包

大数据量（N,V≤1000）：优先二进制优化

存在特殊约束：

需要恰好装满 → 修改初始化

求方案数 → 将max改为+=

求具体方案 → 记录状态转移路径