背包问题是最基础的动态规划问题，本文给出背包的模板代码。

约定背包容量(Capacity): C物品数目( Number of items): N第 i 件物品的占用背包的空间容量(Capacity of item i, 也可以理解为Cost): c_i, 其中1≤i≤N第i件物品的价值(Value of item i): v_i, 其中1≤i≤NF(i,j): 前i个物品, 容量为j的背包下能装的物品的最大价值, 是一个 (N+1)×(C+1) 的矩阵01背包

第i个物品: 要么放0件，要么放1件

伪代码如下:

01背包

可视化如下:

01背包：可视化

上述步骤充分理解后，为节省存储空间，可用一维向量来存储，伪代码如下：

注意:

内层for循环的迭代顺序从大到小矩阵第一行初始化有两种选择：如果不要求装满背包，不装物品对应的价值全部为０，故第一行全部初始化为0;如果要求恰好装满背包，除首元素外，对于j=1,2,...,C容量，不装物品不满足要求，全部初始化为一个负无穷大。完全背包

对于完全背包问题，第i个物品: 可以放任意件，只要不超出背包容量。与01背包不同的，只在于内层for循环的迭代顺序，见下图红色部分：

二维可视化如下，仔细体会：

分组背包

物品有K组，每组内：物品互相冲突，最多选一件。

伪代码如下：

和01背包类似，只是多了一层循环，分别尝试一组内的物品。

依赖背包考虑一个主件和它的附件(假设有n个)集合，可用策略: 2^n+1:1: 不选主件2^n: 选取主件后的策略数所有策略都是互斥的，将该主件和它的附件集合对应的所有策略转换为 分组背包 中的一个物品组，每个物品(策略)有一个cost和value所有费用相同的策略，只取价值最大的策略对主件k的附件集合进行 01-恰好-背包, 得到费用为 0,1,⋯,C−c_k时，对应的最大价值 F转换为一个物品组:应用分组背包算法

注: 公式不太好输入，需要latex pdf版本的，可以私信我。