背包问题是一类经典问题，其本质是0/1线性规划，私以为背包问题的精髓在经典文章《背包九讲》中已基本道尽，本文结合自己有限的理解，总结了一下对最基本的几类背包问题的学习，并整理了相关的代码实现。
一般来讲，背包问题形式如下，有$N$件物品和一个容量为$V$的背包。每件物品有一定的价值和费用。 对物品的放置有一系列的限制条件，求解使价值总和最大的方案。
【0/1背包】
在0/1背包问题中，每个物品有价值$w_i$和费用$c_i$，每个物品只有一件，对每个物品只有选或不选两种选择。
设$f[i][v]$表示前$i$件物品恰放入一个容量为v的背包可以获得的最大价值 转移： $$f[i][v]=max(f[i-1][v],f[i-1][v-c_i]+w_i)$$
状态转移是比较显然的，即我们考虑一个物品放或不放，放的话，我们在花费一定费用同时，获取其价值，若不选，就不选。
可以利用滚动数组优化空间复杂度，我们注意到第$i$行$f[i][v]$只与上一行$f[i - 1][v]$和$f[i - 1][v - c_i]$有关，即我们可以直接用$f[v]$表示将物品放入容量为v的背包可以获得的最大价值，顺序枚举$i$，保证了我们在更新$f[v]$时,$f$数组储存的都是上一行的结果，倒序枚举体积，保证了在访问$f[v - c_i]$都会得到一个未被该物品更新过的价值，也就是说$f[v - c_i]$表示的是一个未曾考虑过物品$i$的子问题结果，也就保证了每个物体都最多都只会被选择一次。
这一点有些难理解，可以与下文中完全背包结合起来仔细想一下。
【0/1背包代码】
为方便，将背包过程抽象出来，写成一个函数。 变量名略有不同，习惯问题。
inline void zeroOnePack(int cost, int benifit){
for(int v = V; v >= cost; v--){
f[v] = std::max(f[v], f[v - cost] + benifit);
}
}
而主过程像这么写：
for(int i = 0; i < N; i++){
zeroOnePack(cost[i], benifit[i]);
}
【完全背包】
在完全背包问题中，物品的数目不限，即可以选择无数件。
显然我们可以把完全背包转化为很多很多件0/1背包物品，但这样时间上不够优。
考虑在0/1背包中我们必须要倒序枚举$v$，这是为了保证每个物品至多被选择一次，而在这里，就没有这个限制了。
与0/1背包代码实现上的唯一区别就是改为顺序枚举$v$。
这一点很有趣，可以结合下图理解：
吐槽：亲手~~mspaint~~制图，简直良心～。
【完全背包代码】
inline void completePack(int cost, int benifit){
for(int v = cost; v <= V; v++){
f[v] = std::max(f[v], f[v - cost] + benifit);
}
}
【多重背包】
多重背包中，限制了物品数量是$n_i$。
显然多重背包也可以转化为$n_i$件0/1背包，但这样时间上依然不够优。
考虑二进制的思想，将该物品拆解为若干件物品，使得这若干件物品与原来物品等价。
具体方法是（引自《背包九讲》）：
将第i种物品分成若干件物品，其中每件物品有一个系数，这件物品的费用和价值均是原来的费用和价值乘以这个系数。使这些系数分别为$1,2,4,...,2^{k-1},n_i-2^k+1$，且$k$是满足$n_i-2^k+1>0$的最大整数。例如，如果 $n_i$ 为 $13$ ，就将这种物品分成系数分别为$1,2,4,6$的四件物品。
我的理解： 就是将$n_i$拆解为若干个2的幂和一个余项的形式，这样就使得$[1, n_i]$中任意件数都可以表示为这几个数的和，这一点是可以证明的，也就是说，这些物品的自由组合与原来物品的不同件数等价，这样就将件数降到了$O(log\ n_i)$的级别，一般来说是可以承受的了。
【多重背包代码】
代码：
inline void multiplePack(int cost, int benifit, int amount){
for(int k = 1; amount > k; amount -= k, k <<= 1){
zeroOnePack(cost * k, benifit * k);
}
zeroOnePack(cost * amount, benifit * amount);
}
关于背包多重背包的单调队列优化解法，还请参见另一篇专门的文章^_^。 传送门-> 多重背包 - 单调队列优化
【混合背包】
依旧是给定背包与物品，不同的是这里的物品可以是以上任意一种类型，即有的只有一件，有的有无数件，有的有若干件。 怎么办呢？
只需要根据种类不同，分别处理就行了。
【混合背包伪代码】
for i in [1, N]:
if 第i件物品是01背包:
zeroOnePack(c[i],w[i])
elif 第i件物品是完全背包:
completePack(c[i],w[i])
elif 第i件物品是多重背包:
multiplePack(c[i],w[i],n[i])
这里就看出抽象成函数的好处了
【二维背包】
这次不同的是，每件物品都有两个代价（比如重量和体积），背包有容量限制也有体积限制，依旧求最优方案。
解决方案也很简单，将原来的方程加一维以满足新的限制，这是比较常见的思想与解决方案。
设$f[v][u]$表示背包中体积为$v$，重量为$u$时的最大价值。 转移时同理，对一件物品，选的话要同时付出两种代价，依照数量的不同类型进行转移即可。
给出一个0/1二维背包的栗子。
【二维背包代码】
inline void zeroOnePack(int benifit, int volume, int weight){
for(int v = V; v >= volume; v--){
for(int u = G; u >= weight; u--){
f[v][u] = std::max(f[v][u], f[v - volume][u - weight] + benifit);
}
}
}
另外的，如果一维背包中题目限制总件数，就可以看作二维背包来解。
【分组背包】
分组背包中物品被划分为若干组，每组中的物品互相冲突，最多选一件。依然求解最优方案。
枚举每个组，决策是是选择本组的某一件，或是一件都不选。
对于每一个组，枚举选哪一件就好。
倒序枚举体积以保证最多选一件，原理与0/1类似。
【分组背包伪代码】
for k in allGroups:
for v in [V..0]:
for i in Group(k):
f[v] = max(f[v], f[v - c[i]] + w[i])
【依赖背包与泛化物品】
依赖背包问题的物品间存在某种“依赖”的关系。也就是说，$i$依赖于$j$，表示若选物品$i$，则必须选物品$j$。
一般的情况是，依赖关系以“森林”的形式给出，也就是说，每个物品最多只依赖于一个物品，且不出现循环依赖。
先说泛化物品。
泛化物品是背包九讲中的精髓，具体内容可以参见原文。
两个泛化物品的和：枚举体积，将其分配给两个物品，取价值之和的最大值。
当两个泛化物品存在交集，即不能同时选择时，我们要考虑两个泛化物品的并，即枚举体积，选取价值较大的那一个。 （泛化物品并 的概念引自 徐持衡 《浅谈几类背包问题》）
至于依赖背包问题，依赖关系树中，每一个子树都等价于一件泛化物品，求某子树对应的泛化物品相当于求其所有儿子的对应的泛化物品之和。
运用树形DP的方式，每个节点都需要先对子节点先求解后才能计算自己的解。
【依赖背包代码】
struct Node{
int cost, value;
int f[MAXV + 1];
Node *child, *next;
Node(){
cost = value = 0;
memset(f, 0, sizeof f);
child = next = NULL;
}
void solve(int V){
for(Node *vi = child; vi; vi = vi->next){
memcpy(vi->f, f, sizeof f);
// 将当前泛化物品的信息传递给子节点，以此作为子节点的起始状态
vi->solve(V - cost);
for(int k = vi->cost; k <= V; k++){
f[k] = std::max(f[k], vi->f[k - vi->cost] + vi->value);
// 求f[v]与vi->f[v]的并，更新到f[v]中。
}
}
}
} vs[MAXN + 1];
inline void addChild(int u, int v){
(vs + v)->next = (vs + u)->child;
(vs + u)->child = vs + v;
}
【总结】
以上就是背包问题中最基础的部分，泛化物品的概念十分精炼，是对背包问题本质的揭示，关于背包问题还有许许多多的扩展和变形，我们还需灵活运用，自我思考，这也是一枚OIer的必备品质。
算法的美无以穷尽，未来的路还有很长，加油！