概览

背包问题可以大致分为三类，分别是：

1. 背包组合问题
2. True/False 问题
3. 最大最小问题

其基础的背包问题一般由两个模型演变而来：

1. 0-1 背包问题
2. 完全背包问题

本文先研究 0-1 背包和完全背包，而后对其他问题进行研究。

例题索引

0-1 背包

问题	类型	递推公式	备注
例题 LC474：1和0	0-1 背包最大最小值问题	dp[i] = max(dp[i], dp[i-num] + 1)	两个背包
例题 LC416：分割等和子集	0-1 背包True/False问题	dp[i] = dp[i] or dp[i - num]
例题 LC494：目标和	0-1 背包组合问题	dp[i] += dp[i - num]
例题 LC1049：最后一块石头的重量 III	0-1 背包最大最小值问题	dp[i] = max(dp[i], dp[i-stone] + stone)