几种背包问题

01背包问题

有$N$个物品和一个容量是$V$的背包。 第$i$个物品的体积是$vi$，价值是$wi$。 求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。

对于每件物品，要进行决策是否装入背包。 因为每件物品只有取和不取两种状态，所以叫做01背包问题

$f[i][j]$ 表示前 $i$ 件物品 背包容量为 $j$ 时的最大价值。

动态规划转移方程：

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

其中i表示前i件物品，j表示当前背包容量为j时。

• 背包装不下第$i$件物品，则f[i][i] = f[i-1][j]

• 背包装得下，如果不选第$i$件物品，则f[i][i] = f[i-1][j]

• 背包装得下，选第$i$件物品，f[i][i] = f[i-1][j-v[i]] + w[i]

循环应该这样写：

for (int i=1;i<=N;i++)
{
    for (int j=1;j<=V;j++)
    {
        if (j < v[i]) f[i][j] = f[i-1][j];
        else f[i][j] = max(f[i-1][j],f[i-1][j-v[i]] + w[i]])
    }
}

初始化： f[0][0] = 0 即0件物品时价值为0

01背包问题优化

因为每一次的 $i$ 只需要从 $i-1$ 状态更新，所以可以压缩为一维数组。

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

同时要将 $j$ 循环倒序，因为 $j-v[i]$ 是严格小于 $j$ 的，倒序可以让每个状态 $i$ 都是由上一层 $i-1$ 的状态更新 即for (int j=V;j>=0;j--)

完全背包问题

在01背包问题的基础上，让每件物品可以取无限次。

动态规划转移方程：

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

与01背包问题不同的只有后面那一项中的i-1变为了i

原本的应该是f[i][j] = max{f[i-1][j] , f[i][j-k*v[i]] + k*w[i]} (k >= 0) 不考虑背包容量的话，$k$ 可以到$+\infty$ 这里很巧妙的是可以转化成上面那个方程。

数学推导：

可以发现，$②$ $+w$ 是 $①$ 式中$f[i-1][j]$右边的式子

所以

循环应该这样写：

for (int i=1;i<=N;i++)
{
    for (int j=1;j<=V;j++)
    {
        if (j < v[i]) f[i][j] = f[i-1][j];
        else f[i][j] = max(f[i-1][j],f[i][j-v[i]] + w[i]])
    }
}

完全背包问题优化

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

但此时不需要 $j$ 循环倒序，因为每次更新第 $i$ 层也是从第 $i$ 层来的，也就是上面的f[i][j-v[i]]

多重背包问题

第 $i$ 种物品最多有 $si$ 件，每件体积是 $vi$，价值是 $wi$。

在01背包问题的基础上，让每件物品可以取一定次数。

动态规划转移方程 (已优化) ：

f[j] = max{f[j] , f[j-k*v[i]] + k*w[i]} (k >= 0 && k <= s && k * v <= j)

在范围内枚举 $k$ 的取值

多重背包问题的二进制优化：

思想：对于每一种物品，可以取 $0$ ~ $k$ 个，把取的每一种看做一个新的物品，体积是 $k\times v$ ，价值是 $k \times w$ ，又因为每一个数都可以用二进制形式表示，即0~k之间的任何一个数都可以拆成2的次方和形式。所以，枚举这 $k$ 个物品，只用枚举 $\log_{2}{k}$ 个物品。后面的操作就和01背包问题相同了。

分组背包问题

有 $N$ 组物品和一个容量是 $V$ 的背包。

每组物品有若干个，同一组内的物品最多只能选一个。

多重背包问题是分组背包问题的一种特殊情况

动态规划转移方程 (已优化) ：

f[j] = max(f[j],f[j - v[k]] + w[k]) (k >= 0 && k <= s) 需要循环 $k$ 的取值来枚举一组内的每一件物品

循环应该这样写：

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

总结

这四种背包问题其实有一定联系。01背包是其中最特殊，也是最基础的问题，每一件物品只有拿与不拿两种状态。分组背包问题里，每一组里的物品是互斥的，只能选一件拿，所以需要在每一组内枚举每一件物品多重背包问题就可以看成是在每一组里面的物品都是同一件物品的不同倍数件，而完全背包问题则和之前的关联性比较小，因为每一件物品可以取无数次，难以通过枚举实现。

代码需要注意这几点：

• 01背包问题的一维方程需要逆序，完全背包则是顺序
• 多重背包的二进制优化需要注意，将一个数拆成二的次方和的时候，它本身要不断减去二的次方，最后剩下的数直接作为一种。 如：$10 = 1 + 2 + 4 + 3$ ，通过 $1、2、4、3$ 这四个数便可以组合成所有 $0$~$10$ 之间的任意数字。
• 分组背包也是逆序，并且注意判断条件j >= v[k]。

例题：