一般来讲都是先学习01背包再去学习完全背包，但是刘汝佳在紫书中由完全背包引入到01背包，看完之后感觉这种学习路线确实可以帮助我们更好地去理解动态规划。lrj nb。

引入 硬币问题

有$n$种硬币，面值分别为$V_1, V_2, …, V_n$，每种都有无限多。给定非负整数S，

可以选用多少个硬币，使得面值之和恰好为$S$？输出硬币数目的最小值和最大值。

$1≤n≤100，0≤S≤10000，1≤V_i≤S$。

经典的DAG问题。

f[cur]表示 current node（面值为$cur$时）距离终点的最短距离

这里我们设终点为0，起点为S,很容易写出状态转移方程

for(int j = 1; j <= n ;++j){
    if(cur >= v[j])f[cur] = max(f[cur],f[cur - v[j]] + 1);
}

进化 完全背包问题

有$n$种物品，每种均有无穷多个。第$i$种物品的体积为$V_i$，重量 为$W_i$。选一些物品装到一个容量为$C$的背包中，使得背包内物品在总体积不超过$C$的前提下重量尽量大。$1≤n≤100，1≤V_i≤C≤10000，1≤W_i≤10^6$。

和硬币问题非常非常相似,只不过“面值之和恰好为S”改成了“体积 之和不超过C”，另外增加了一个新的属性——重量，相当于把原来的无权图改成了带权图 （weighted graph）。这样，问题就变为了求以C为起点（终点任意）的、边权之和最大的路径。

与前面相比，DAG从“无权”变成了“带权”，但这并没有带来任何困难，此时只需将某处代码从“＋1”变成“＋$w[ i ]$”即可。

for(int j = 1; j <= n ;++j){
    if(cur >= v[j])f[cur] = max(f[cur],f[cur - v[j]] + w[j]);
}

最终 01背包问题

有$n$种物品，每种只有一个。第$i$种物品的体积为$V_i$，重量 为$W_i$。选一些物品装到一个容量为$C$的背包中，使得背包内物品在总体积不超过$C$的前提下重量尽量大。$1≤n≤100，1≤V_i≤C≤10000，1≤W_i≤10^6$。

​ 对于当前的问题，01背包已经不适用了。只凭借“剩余体积”这个状态，无法得知每一个物品是否已经用过，也就无法知道在当前节点想要转移到其他节点时是否可以转移。在原来无穷多种物品的前提下状态转移十分混乱，在任何时候都允许使用任何一种物品，难以控制。为了消除这种混乱，需要让状态转移（即决策）有序化。

​ 引入“阶段”这个概念之后，状态转移就变得有序了。

用f[i][j]表示当前位于第$i$ “阶段“，背包剩余容量为j时接下来的最大重量和。

转移决策有两种：

​ 1.不装入当前阶段物品

​ 2.装入当前阶段的物品

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

更通俗一点的说法是，f[i][j]表示将第$i,i + 1,i + 2 … … n$ 个物品放入容量为j的背包中的最大重量

事实上，这个说法更加常用——“阶段”只是辅助思考的，在动态规划的状态描述中最好避免“阶段”、“层”这样的术语。很多教材和资料直接给出了这样的状态描述，如果对此理解不够深入，很容易出现“每次碰到新题自己都想不出来，但一看题解就懂”的尴尬情况。

变形 && 优化

在很多情况下记忆化搜索程序更加的直观，易懂，但是在01背包中递推法更加理想，因为当对“阶段”进行定义之后，“阶段”本身就提供了一个天然的计算顺序。

for(int i = n; i >= 1; --i){
     for(int j = 0; j <= V; ++j)}{
        f[i][j] = (i == n?0:f[i + 1][j]);
        if(j >= v[i])f[i][j] = max(f[i][j],f[i + 1][j - v[i]] + w[i]);
    }
}

如果我们对上面的定义方式选择对称的转移方向，那么我们就会得到一种更常见的定义方式。

实际上f[i][j]更常见的含义是：在$1 - i$号物品中选择，装入到体积至多为$j$的背包中所能取到的最大重量。

for(int i = 1; i <= n ; ++i){
    for(int j = 0; j < = V; ++j){
        f[i][j] = (i == 1?0:f[i - 1][j]);
        if(j >= v[i])f[i][j] = max(f[i][j],f[i - v[i]] + w[i]);
    }
}

上面的两种定义方式基本是完全对称的，但是有一点微小的区别是第二种定义方式对阶段的遍历是正序的，这样就意味着我们可以一边读入$v,w$一边计算而不需要先把$v,w$保存下来。

P.S. 滚动数组优化：

在递推法中，如果计算顺序很特殊，而且计算新状态所用到的原状态不 多，可以尝试用滚动数组减少内存开销。在使用滚动数组后，解的打印变得困难了，所以在需要打印方案甚至要求字典序最小方案的场合，应慎用滚动数组。