背包问题通常采用递推方式实现。
背包问题也属于线性dp，但是有别于朴素的线性dp。 背包问题的状态是二维的，而所处线性空间是一维的（状态中多出一个物品体积的维度），复杂的线性dp通常都是状态维度比线性空间多了一个维度，对于这样的题目，背包问题是一个很好的样例。
在讨论背包问题之前，首先介绍二维状态的滚动数组优化方法。
对于二维状态，如果f[i][j]的计算只需要i之前k-1行以及i行j之前或j之后其中之一的信息，
那么就可以使用动态数组压缩到一维状态，用k个一维数组f[n]代替二维数组f[m][n]，
让j从前向后遍历（需要i行j之前信息）或者让j从后向前遍历（需要i行j之后信息）即可。
具体来讲，如果计算f[i][j]需要i之前k-1行以及i行j之前的信息，那么创建数组f[k][n]，使用如下算法来递推：
for(i = 1; i <= m; i++)
for(j = 1; j <= n; j++)
// 原来的f[i][j]变为f[i % k][j]，i之前t行为f[(i-t) % k][1...n]，i行j之前为f[i % k][1...j]
事实上，滚动数组更常用的形式是：只使用1个一维数组f[n]代替二维数组f[m][n]，
也就是说f[i][j]的计算只需要i之前1行以及i行j之前或j之后其中之一的信息。
如果j从前向后遍历，滚动数组在计算f[i][j]时存储的数据是：
f[i][1] ...... f[i][j-1] f[i-1][j] ...... f[i-1][m]
如果j从后向前遍历，滚动数组在计算f[i][j]时存储的数据是：
f[i-1][1] ...... f[i-1][j] f[i][j+1] ...... f[i][m]
所以，如果f[i][j]的计算只需要用到f[i-1][j...m]和f[i][1...j-1]，则让j从前向后遍历即可；如果f[i][j]的计算只需要用到f[i-1][1...j]和f[i][j+1...m]，则让j从后向前遍历即可。
现有n件物品，每件物品只有1个，物品i的体积为v[i]，物品i的价值为w[i]，要装入容量为m的背包中，求背包可装入的最大价值。
将问题的解用在前n个物品中选，体积和$\leqslant$ j的所有选法的最大价值这一集合属性来表达。
原子集合属性（在前i个物品中选，1 $\leqslant$ i $\leqslant$ n，体积和$\leqslant$ 0的所有选法的最大价值、在前0个物品中选，体积和$\leqslant$ j，1 $\leqslant$ j $\leqslant$ m，的所有选法的最大价值）可以直接得出为0。
小一级集合的属性到大一级集合的属性的推导式为：
\[f[i][j] = max \left\{ \begin{aligned} &f[i-1][j]&&\text{(不选物品i)}\\ &f[i-1][j-v[i]]+w[i]&&\text{(选物品i)} \end{aligned} \right.\]0/1背包f[i][j]的计算只需要用到f[i-1][1...j]，让j从后向前遍历即可。
// 原子集合初始化：f[j] = 0 (0<=j<=m)，在前0个物品中选、体积和<=j的所有选法的最大价值可以直接得出为0
for (int i = 1; i <= n; i++)
for (int j = m; j >= v[i]; j--)
f[j] = max(f[j], f[j - v[i]] + w[i]);
// 最终结果：f[m]
现有n件物品，每件物品有无穷个，物品i的体积为v[i]，物品i的价值为w[i]，要装入容量为m的背包中，求背包可装入的最大价值。
将问题的解用在前n个物品中选，体积和$\leqslant$ j的所有选法的最大价值这一集合属性来表达。
原子集合属性（在前i个物品中选，1 $\leqslant$ i $\leqslant$ n，体积和$\leqslant$ 0的所有选法的最大价值、在前0个物品中选，体积和$\leqslant$ j，1 $\leqslant$ j $\leqslant$ m，的所有选法的最大价值）可以直接得出为0。
小一级集合的属性到大一级集合的属性的推导式为：
\[f[i][j] = max \left\{ \begin{aligned} &f[i-1][j]&&\text{(不选物品i)}\\ &f[i-1][j-k*v[i]]+k*w[i]&&\text{(选k个物品i)} \end{aligned} \right.\]完全背包f[i][j]的计算只需要用到f[i-1][1...j]，让j从后向前遍历即可。
// 原子集合初始化：f[j] = 0 (0<=j<=m)，在前0个物品中选、体积和<=j的所有选法的最大价值可以直接得出为0
for (int i = 1; i <= n; i++)
for (int j = m; j >= 0; j--)
for (int k = 1; k*v[i] <= j; k++)
f[j] = max(f[j], f[j - k*v[i]] + k*w[i]);
// 最终结果：f[m]
通过上面的推导，完全背包递推式得到进一步优化，此时，完全背包f[i][j]的计算需要用到f[i-1][j]和f[i][1...j-1]，让j从前向后遍历即可。
// 原子集合初始化：f[j] = 0 (0<=j<=m)，在前0个物品中选、体积和<=j的所有选法的最大价值可以直接得出为0
for (int i = 1; i <= n; i++)
for (int j = v[i]; j <= m; j++)
f[j] = max(f[j], f[j - v[i]] + w[i]);
// 最终结果：f[m]
现有n件物品，物品i的个数为s[i]，物品i的体积为v[i]，物品i的价值为w[i]，要装入容量为m的背包中，求背包可装入的最大价值。
将问题的解用在前n个物品中选，体积和$\leqslant$ j的所有选法的最大价值这一集合属性来表达。
原子集合属性（在前i个物品中选，1 $\leqslant$ i $\leqslant$ n，体积和$\leqslant$ 0的所有选法的最大价值、在前0个物品中选，体积和$\leqslant$ j，1 $\leqslant$ j $\leqslant$ m，的所有选法的最大价值）可以直接得出为0。
小一级集合的属性到大一级集合的属性的推导式为：
\[f[i][j] = max \left\{ \begin{aligned} &f[i-1][j]&&\text{(不选物品i)}\\ &f[i-1][j-k*v[i]]+k*w[i], 1\leqslant k\leqslant s[i]&&\text{(选k个物品i)} \end{aligned} \right.\]多重背包f[i][j]的计算只需要用到f[i-1][1...j]，让j从后向前遍历即可。
// 原子集合初始化：f[j] = 0 (0<=j<=m)，在前0个物品中选、体积和<=j的所有选法的最大价值可以直接得出为0
for (int i = 1; i <= n; i++)
for (int j = m; j >= 0; j--)
for (int k = 1; k <= s[i] && k*v[i] <= j; k++)
f[j] = max(f[j], f[j - k*v[i]] + k*w[i]);
// 最终结果：f[m]
多重背包还可以用倍增思想优化，详见倍增。
现有n种物品，种类i的物品个数为s[i]，种类i中的物品j的体积为v[i][j]，种类i中的物品j的价值为w[i][j]，要装入容量为m的背包中，求背包可装入的最大价值。
将问题的解用在前n种（注意是前n种，不再是前n个）物品中选，体积和$\leqslant$ j的所有选法的最大价值这一集合属性来表达。
原子集合属性（在前i种物品中选，1 $\leqslant$ i $\leqslant$ n，体积和$\leqslant$ 0的所有选法的最大价值、在前0种物品中选，体积和$\leqslant$ j，1 $\leqslant$ j $\leqslant$ m，的所有选法的最大价值）可以直接得出为0。
小一级集合的属性到大一级集合的属性的推导式为：
\[f[i][j] = max \left\{ \begin{aligned} &f[i-1][j]&&\text{(不选物品i)}\\ &f[i-1][j-v[i][k]]+w[i][k], 1\leqslant k\leqslant s[i]&&\text{(选种类i的物品k)} \end{aligned} \right.\]分组背包f[i][j]的计算只需要用到f[i-1][1...j]，让j从后向前遍历即可。
// 原子集合初始化：f[j] = 0 (0<=j<=m)，在前0个物品中选、体积和<=j的所有选法的最大价值可以直接得出为0
for (int i = 1; i <= n; i++)
for (int j = m; j >= 0; j--)
for (int k = 1; k <= s[i]; k++)
if (v[i][k] <= j)
f[j] = max(f[j], f[j - v[i][k]] + w[i][k]);
// 最终结果：f[m]