经典之二：背包问题

· · 个人记录

咳咳，今天下午就先搞动态规划怎么样。

说完了数字三角形，我们再来说说背包问题 话说DD大牛为什么那么强啊啊啊我弱死了，所以为什么我要说背包问题QAQ悔恨的泪水。

其实不论你什么样的问题，只要它是个背包问题，本质上都可以转化成零一背包，所以我们就从零一背包开始讲起。

有 n 种物品，每种均有一个。第 i 种物品的体积为 Vi ，重量为 Wi 。选一些物品装到一个容量为 C 的背包中，使得背包内物品在总体积不超过 C 的前提下重量尽量大。

首先，可以确定的一点是：每件物品我都要考虑到底把不把它“偷走”，拿走不划算的物品肯定会使我们最终得到的总价值最小。那么对于一件物品，就只有拿走和不拿走两种状态；我们现在需要解决的是，不同的物品间如何进行状态的转移。

由于我们不能根据物品的属性确定考虑的顺序，那我们不妨就从头到尾一件一件考虑。

同时，物品的限制属性是体积，那我们把它与物品的序号结合起来考虑，可以得到这样一个状态定义：f[i][j] 表示前 i 件物品恰放入一个容量为 j 的背包中所能得到的最大重量。

我们现在就只需要考虑第 i 件物品的决策；如果我们不拿走它，当前状态就与 f[i - 1][j] 相同；如果我们拿走它，这意味着我们在考虑第 i - 1 件物品时，背包必须还剩 j - v[i] 的容量 否则你想拿走也拿不走啊是吧 。

那么，状态转移方程即可得出：f[i][j] = max(f[i - 1][j], f[i - 1][j - v[i]] + w[i]) 逆序枚举。

接下来我们再来看完全背包问题：

有 n 种物品，每种均有无穷多个。第 i 种物品的体积为 Vi ，重量为 Wi 。选一些物品装到一个容量为 C 的背包中，使得背包内物品在总体积不超过 C 的前提下重量尽量大。

首先我把状态转移方程写出来：f[i][j] = max(f[i - 1][j], f[i - 1][j - v[i]] + w[i]) 顺序枚举。

相信眼尖的同学已经找出来了不同，但是为什么这样修改即可呢？

这个问题与零一背包唯一的区别就在于物品个数无限，换句话说，我们无论考虑哪一件物品，都不需要考虑其他物品是否对它构成了约束。这个约束指的是物品件数，当我们逆序枚举时，就隐式地保证了之前的状态里绝对没有选入过第 i 件物品；所以我们顺序枚举的话，就解除了这个限制，也就符合了物品个数无限的条件。

以上均为口胡QAQ不要管我 我控制不住我自己啊啊啊

再然后我们来看空间优化问题：

你快给我把数组压成一维！！！

呃，不要慌张，既然你问了，我肯定会想办法解答是吧。

那我们保留哪个维度呢？答案是 f[i][j] 中的 [j] 。因为背包问题中我们需要的往往是上一阶段的状态。

零一背包中，我们需要的是第 i - 1 件物品的状态，所以逆序枚举可以保证此时的 f[j - v[i]] 是上一件物品对应的；顺序枚举就保证了这是当前这一件物品对应的状态。

先把代码扔在最后。

void zop(int cost, int weight)
{
    for (int j = v; j >= cost; j--)
        f[j] = max(f[j], f[j-cost] + weight);
    return;
} // 零一背包

void cp(int cost, int weight)
{
    for (int j = cost; j <= v; j++)
        f[j] = max(f[j], f[j-cost] + weight);
    return;
} // 完全背包

然后我们再来看一个叫做多重背包的问题：

有 n 种物品，第 i 种物品的数量为 Ni 。第 i 种物品的体积为 Vi ，重量为 Wi 。选一些物品装到一个容量为 C 的背包中，使得背包内物品在总体积不超过 C 的前提下重量尽量大。

惊不惊喜意不意外？是不是发现不同之处还是在于物品的数量不同？那你先仔细想想，我们能不能借助于之前相似的状态定义解决这个问题。

答案当然是能。我们可以把第 i 种物品看成 Ni 种物品，只不过它们的体积和重量都相同，这样就可以利用零一背包的方法解决；但是这样做显然时间和空间复杂度都不占优，所以我们要改善物品拆分的策略：借助二进制的思想。

具体来说，第 i 种物品其实就等价于一个体积为 Vi ＊ Ni ，重量为 Wi ＊ Ni 的物品，同理我们也可以把它拆成1， 2， 4······件物品的组合，然后再进行零一背包。

值得注意的是，如果一种物品未拆分前其总体积就已经超过了背包容量，那么相对而言它就有无限件，此时需要对其进行完全背包的处理。

代码在这里：

void mp(int cost, int weight, int amount)
{
    if (cost * amount >= v)
    {
        cp(cost, weight); return;
    }
    int k = 1;
    while (k < n)
    {
        zop(k * cost, k * weight);
        amount = amount - k;
        k = k * 2;
    }
    zop(amount * cost, amount * weight);
    return;
} // 多重背包

然后嘛，当然还没完，前辈有云：

有向无环图上的动态规划是学习动态规划的基础。很多问题都可以转化为DAG上的最长路、最短路或路径计数问题。

所以我们来研究一下如何把背包问题向这个方向转化 前辈是真的强QWQ我等永远只可膜拜 。

请继续阅读《经典之三》 其实是我为了平均篇幅扔过去的 。

引用资料：《算法竞赛入门经典》《背包九讲》