算法-背包DP

4FGR2025-04-152025-04-15

背包DP

引入

在具体讲何为背包dp前，先来看如下的例题：

Charm Bracelet

题 意 概 要 ： 有 个 物 品 和 一 个 容 量 为 的 背 包 ， 每 个 物 品 有 重 量 和 价 值 两 种 属 性 ， 要 求 选 若 干 物 品 放 入 背 包 使 得 背 包 中 的 物 品 的 总 价 格

在上述例题中，由于每个物体只有两种可能的状态（取与不取），对应二进制中的0和1，这类问题便被称作0-1背包问题。

0-1背包

解释

例题中已知条件有第i个物品的重量，价值以及背包的总重量。

设DP状态为在只能放前个物品的情况下，容量为的背包所能达到的最大总价值。

考虑转移。假设当前已经处理好了前个物品的情况下，那么对于第个物品当其不放入背包时，背包的剩余容量不变，背包中物品的总价值也不变，故这种情况的最大价值为 $f{i-1,j} $；当其放入背包时，背包的剩余容量会减小$ w_i $背包中物品的总价值会增大$ v_i $，故这种情况的最大价值为$ f{i-1,j-w_{i}}+ v_i$

由此可以得出状态转移方程：

$f_{i,j} = max(f_{i-1,j},f_{i-1,j-w_i}+v_i)$

这里如果直接采用二维数组对状态进行记录，会出现MLE。可以考虑改用滚动数组的形式来优化。由于对 $fi $有影响的只有$ f{i-1} $可以去掉第一维，直接用$ f_i $来表示处理到当前物品时背包容量为$ i$ 的最大价值，得出以下方程:

$f_j = max(f_j,f_{j-w_i}+v_i)$

务必牢记并理解这个转移方程，因为大部分背包问题的转移方程都是在此基础上推导出来的。

实现

for(int i=1; i<=n; i++){
    for(int l= W; l>=w[i];l--){
        f[l] = max(f[l],f[l-w[i]]+ v[i]);
    }
}

完全背包

解释

完全背包模型与背包类似，与背包的区别仅在于一个物品可以选取无限次，而非仅能选择一次。

我们可以借鉴背包的思路，进行状态定义：设为只能选前个物品时，容量为的背包可以达到的最大价值。

需要注意的是，虽然定义与背包类似，但是其状态转移方程和并不相同。

过程

可以考虑一个朴素的做法：对于第件物品，枚举其选了多少个来转移。这样做的时间复杂度时的。

状态转移方程如下：

$f_{i,j} = \max\limits_{k=0}^{+\infty} \left(f_{i-1,j-k\times w_i} + v_i\times k\right)$

考虑做一个简单的优化。可以发现，对于 $f{i,j} $，只要通过$ f{j,j-w_i}$ 转移就可以了。因此状态转移方程为：

$f_{i,j} = \max(f_{i-1,j}, f_{i,j-w_i}+v_i)$

理由时当我们这样转移时，$f{i,j-w_i} $已经由$ f{i,j}-2\times wi $更新过，那么$ f{i,j-w_i} $就是充分考虑了第$ i$ 件物品所选次数后得到的最优结果。换言之，我们通过局部最优子结构的性质重复使用了之前的枚举过程，优化了枚举的复杂度。