作为经典的动态规划问题，背包问题有许多变形。掌握基本模型对理解、解决动态规划问题有很大帮助。其中有一篇广为流传的教程——《背包九讲》。后面一部分我还没有完全看懂，不过先把看懂的部分简要概括一下。

01背包

条件

有N件物品和一个容量为V的背包。第i件物品的费用是c[i],价值是w[i]。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量,且价值总和最大。（后面命名方式基本相同）

每一种物品只有一件,物品相互独立，只有放或不放两种情况。

思路

对于任何一件物品i，只能有两种情况——放或不放。定义f[i][v]表示前i件物品放入容量v的背包能获得的最大价值。那么如果物品i放入背包，f[i][v]=f[i-1][v-c[i]]+w[i]，否则f[i][v]=f[i-1][v]。

状态转移方程

f[i][v]=max{f[i-1][v],f[i-1][v-c[i]]+w[i]}

即

1
2
3
for(i = 1 ; i <= N ; i++)
    for(v = V ; v > 0 ; v--)
        f[v] = max(f[v], f[v-c[i]]+w[i]);

完全背包

条件

每种物品都有无限件可以使用。

状态转移方程

f[i][v]=max{f[i-1][v],f[i][v-c[i]]+w[i]}

即

1
2
3
for(i = 1 ; i <= N ; i++)
    for(v = 0 ; v <= V ; v++)
        f[v] = max(f[v], f[v-c[i]]+w[i]);

（只需改变一下v的方向）

多重背包

条件

物品i最多有n[i]件可用。

思路

数组多一维记录物品数量，用类似完全背包的方法求解。也可以把物品平摊开来，当做01背包求解。

状态转移方程

f[i][v]=max{f[i-1][v-k*c[i]]+k*w[i]|0<=k<=n[i]}

即

1
2
3
4
5
for(i = 1 ; i <= N ; i++)
    for(v = 0 ; v <= V ; v++)
        for(k = 1 ; k <= n[i] ; k++)
            if(v-k*c[i] >= 0)        
                f[v] = max(f[v], f[v-k*c[i]]+k*w[i]);

这只是最直观的大概样式，可以用二进制拆分或单调队列进行优化。

混合背包

条件

即将上面三种问题混合起来，有的物品只有一个，有的有多个，有的有无限个。

思路

判断一下就完了，略。

多维背包

条件

拿二维01背包做例子，其他同理。

对于每个物体，有两种不同的费用。对于物品i，设两种费用为a[i]和b[i]，背包的两种容量为分别为V、U。

思路

将状态也增加一维即可。

状态转移方程

f[i][v][u]=max{f[i-1][v][u],f[i-1][v-a[i]][u-b[i]]+w[i]}

即

1
2
3
4
for(i = 1 ; i <= N ; i++)
    for(v = V ; v > 0 ; v--)
        for(u = U ; u > 0 ; u--)
            f[v][u] = max(f[v][u], f[v-a[i]][u-b[i]+w[i]);

分组背包

条件

物品被分为了几个组，每一组中的物品互相冲突最多只能选其中之一。

思路

显然，将物品分好组遍历就行。

状态转移方程

f[k][v]=max{f[k-1][v],f[k-1][v-c[i]]+w[i]|物品i属于第k组}

即

1
2
3
4
5
6
7
8
9
10
int *p, group[maxk][maxi];
...
for(k = 1 ; k <= K ; k++)
    for(v = V ; v > 0 ; v--){
        p = group[k];
        while(*p){
            f[k][v] = max(f[k-1][v], f[k-1][v-c[*p]]+w[*p]);
            p++;
        }
    }

（假设为01背包） （注意这里将f数组加一维储存k以前的状态只是为了直观一点，其实只需要多一层用来储存k-1时的状态就行了）

依赖背包

条件

物品之间有依赖关系。即，要选i则必须选j。

思路

首选考虑简化的问题。我们假设没有物品既依赖于别的物品又被其他物品依赖，也没有某件物品同时依赖于多个物品。并且假设为01背包。

对于不依赖于其他物品的物品，我们称之为“主件”，其他则称之为“附件”。那么所有物品就分为了几个含有一个主件和若干个附件的集合。对于每个集合，可以都不取、只取主件或取主件和若干个附件。显然，每一个集合中，只可能有一种策略。那么这个问题就可以转化为上面所说的类似于物品组的问题。为了降低复杂度，可以在集合内部先进行一次01背包，去掉很多没用的策略，之后再用分组背包的思路求解。

那么对于更一般的问题呢？如果依赖以森林的方式出现，即附件也可以有附件，那么这就成了一种树型dp。可能要把dfs也结合进去，父节点对字节点的属性都要进行dp。对一层dp，“物品”的值并不确定，那么可以把这种情况称为“泛化物品”，下面进行介绍。

泛化物品

条件

物品没有固定的价值，而是随着分配给它的费用二变化，即价值为费用的函数。

思路

其实上面的物品组也可以说是一种泛化物品，对于一个组，可以用某种费用换取其价值。

那么对于泛化物品，也可以用相似的方法求解，只不过要考虑费用变化的定义域。每一个物品都成了函数，灵活性大大提升。

背包问题的变化

背包问题能有的变化太多了，比如max变min，考虑取物品的顺序、字典序，求方案数量，还可以与其他类型的问题结合，或是用隐秘的问法。这个……我等菜鸡怎敢妄言呢……