2016 November 10

背包问题

01背包

有一个容量为v的背包和n件物品，第i件物品的体积为c[i]，价值为w[i]，求背包能容纳的最大价值。

基本思路

这是最基础的背包问题，特点是每种物品只有一件，可以选择放或者不放。

设f[i,j]表示在前i件物品中选择放入容量为j的背包可以获得的最大值，则有转移方程：f[i,j] = max{f[i-1,j], f[i-1,j-c[i]] + w[i]}。

for i = 1 to n
    for j = 1 to v
        f[i][j] = f[i-1][j];
        if (j >= c[i])
            f[i][j] = max(f[i][j], f[i-1][j-c[i]] + w[i]);

该方法的时间和空间复杂度均为O(nv)，不但能求出最大价值，通过f矩阵还可逆推出取最大价值时选择了哪些物品。

空间优化

由状态转移方程可知，f[i,j]是由f[i-1,j]和f[i-1,j-c[i]]推出来的，如果主循环中以j递减顺序计算f[i,j]，那么变成由f[i,j]和f[i,j-c[i]]递推，将空间复杂度优化到O(v)。

for i = 1 to n
    for j = v to c
        f[j] = max(f[j], f[j-c] + w);

初始化

初始化f数组的含义可以理解为在没有任何物品可选时的合法状态。

这个初始化技巧可推广到其他类型的背包问题。

装满方案数

换个问法，不考虑背包所容纳的价值，问恰好将背包装满的方案数有多少？可以用类似的做法：对于第i件物品，如果不选，则方案数为f[j-1]；如果选，则方案数为f[j-c[i]]，总方案数为两者之和，因此有状态转移方程f[j]=f[j-1]+f[j-c[i]]。

f[0] = 1;
for i = 1 to n
    for j = v to c
        f[j] = f[j] + f[j-c[i]];

抽象提炼

def ZeroOnePack(c, w)
    for j = v to c
        f[j] = max(f[j], f[j-c] + w)

for i = 1 to n
    ZeroOnePack(c[i], w[i])

完全背包

有一个容量为v的背包和n种物品，第i种物品的体积为c[i]，价值为w[i]，每种物品都有无限多件，求背包能容纳的最大价值。

解决办法

完全背包也是一个十分基础的背包问题，代码与01背包的区别仅在于j的循环顺序。

def CompletePack(c, w)
    for j = c to v
        f[j] = max(f[j], f[j-c] + w);

for i = 1 to n
    CompletePack(c[i], w[i]);

01背包中为何要让j以递减的顺序来循环呢？这是为了保证状态f[i,j]由f[i-1,j]和f[i-1,j-c[i]]递推而来，换句话说，这正是为了保证每件物品只选一次，保证在考虑选入第i件物品这个策略时，依据的是一个绝无已经选入第i件物品的子结果f[i-1,j-c[i]]。而在完全背包中，物品有无限件，在考虑加选一个第i种物品这个策略时，恰恰需要一个可能已入选第i种物品的子结果f[i,v-c[i]]，所以可以且必须以j递增的顺序循环。

装满方案数

如不考虑背包容纳价值，仅要求把背包装满，问有多少种方案？与01背包装满方案数求法类似，也可递推求解，状态转移方程只需将上一节的max改成sum即可。初始化应置f[0]=1，即余为-oo。

混合背包

有n种物品和一个容量为v的背包，第i种物品最多有m[i]件可用，每件占用体积为c[i]，价值为w[i]，求背包所能容纳的最大价值。

解决思路

采用倍增法对各种物品进行组合，转化为01背包问题。

def MultiPack(f[], c, w, m)
    if c * m >= v
        CompletePack(c, w)
    else
        k = 1
        while k < m
            ZeroOnePack(kc, kw)
            m = m - k
            k = k * 2
        ZeroOnePack(mc, mw)

分组背包

有n件物品和一个容量为v的背包，第i价物品的体积为c[i]，价值为w[i]，这n件物品被划分为k组，每组中的物品相互冲突，最多只能选一件，求背包所能容纳的最大价值。

对于每组物品可做的选择有：选择本组中的某一件，或者一件都不选。设f[k,v]表示容量为v时前k组物品能取得的最大价值，那么f[k,v] = max{f[k-1, v], f[k-1, v-c[i]] + w[i] | for i in group k}。

for i = 1 to k
    for j = v to 0
        for x in group[i]
            f[j] = max(f[j], f[j-c[x]] + w[x])

注意循环顺序，它保证了每组内的物品最多只有一个会被放进背包中。

Table of Contents