P1064 金明的预算方案 • CoderXL's Blog

众所周知，背包问题有非常多变种，但万变不离其宗：求解 $\max_{S \subset \Omega} \sum_{i\in S} v_i$ ，在满足 $\sum_{i\in S} w_i \le W$ 和一系列额外的限制条件下。

不说人话？其实就是给定物品全集，物品代价（或者体积/重量）能线性叠加，而题目要求总代价不超过一个预先设定的 $W$ ，在此条件下找到一个子集，最大化总得益。

此处的得益，即 $\sum_{i\in S} v_i$ ，也可以换成其他满足交换律与结合律的运算。

朴素#

这真的是最朴素的算法吧： $O(2^n)$ 地枚举所有的子集，然后再 $O(n)$ 地验证是否满足条件，再更新答案。总复杂度 $O(n2^n)$ . 这种方法显然可以解决一切背包问题，但是具有指数级复杂度。

优化#

在经典的背包问题中，物品价值是实数的线性叠加（正整数也是实数🤣），这意味着它们不仅满足加法交换律，还具有某种单调递增特性。

最优子结构#

为了理解这种单调递增特性，我们先举一个简单的例子：

给定一列实数，请你选择它的一个子序列（不要求连续），使得这个子序列的和最大。

这个问题十分直白，解法也非常简单，那就是求原序列中所有正数的和。

但是我们是如何思考这个问题的？在这个简单例子的求解过程中，我们实际上维护了一个答案数字 $ans$ ，然后遍历原序列 $a[i]$ ，每次 $ans \gets \max\{ans, ans + a[i]\}$ （这个式子就相当于把所有正数都加起来）。

我们这么做的底气是， $ans$ 作为「已遍历部分的最大子序列和」，当遍历到一个新的 $a[i]$ 时，新的 $ans$ 一定来自上一时刻的 $ans$ .

对比下面的这个例子就可以知道，为什么这个高亮的条件不一定满足：

给定一列实数，请你选择它的一个子序列（不要求连续），使得这个子序列的积最大。

如果我们每次仍然按照 $ans \gets \max\{ans, ans \times a[i]\}$ 来更新，就错了。因为新的「最大子序列积」，不一定来自上一时刻的「最大子序列积」。事实上，如果 $a[i]<0$ ，那么它可以与「之前的某个负的子序列积」相乘，负负得正，成为比 $ans\times a[i]$ 还大的「最大子序列积」。而「之前的某个负的子序列积」会提前被 $ans$ 抛弃掉。这就是为什么新的 $ans$ 不一定来自上一时刻的 $ans$ .

这种情况下我们的处理方式就会复杂一些，此处不展开了。

因此，这两个例子想说明的就是，如果答案的性质满足这样的“单调递增特性”： “下一个阶段的最优解一定来自上一个阶段的最优解”，或者“父问题的最优解一定来自子问题的最优解”，那么我们就只需要维护最优解们，然后在最优解上往后递推。显然，子问题的最优解的数量远小于子问题的所有解的数量，因此我们大幅减少了需要考虑的解的规模，复杂度显著降低。

以上的这种“单调递增特性”，我们称为最优子结构，是动态规划的基本条件之一。

构造最优子结构——无后效性#

不是所有问题都天然满足最优子结构，但是通过合理的划分，有可能把原问题划分成满足最优子结构的多个问题。

回到我们的背包问题，其实就是在刚刚的“最大子序列和”问题的基础上，附加了一个代价限制。这导致我们的解不再满足最优子结构：“考虑了前 $i$ 个物品”的「满足限制的最优解」（记作 $ans_{i}$ ），不一定来自“考虑了前 $i-1$ 个物品”的「满足限制的最优解」（记作 $ans_{i-1}$ ）。

这是因为，由于限制的存在，我们无法保证上述两个最优解之间能合法转移而不超过限制。实际上，如果 $ans_{i-1}$ 已经达到了 $W$ 的限制，那么 $ans_i$ 是无法在 $ans_{i-1}$ 的基础上继续叠加 $v_i$ 的。它只能退而求其次，在次优解的海洋中找到一个能不超过限制的较优解，然后叠加上去。

前文说过，全部解的数量远大于最优解的数量，因此我们一旦无法在最优解上递推，复杂度就会非常高。

但是，得益于背包问题中的代价 $w_i$ 是正整数，我们可以把原问题拆成单独的 $W+1$ 个问题：“代价不超过 $\mathscr{W}$ 时，价值总和最大是多少？”，其中 $\mathscr{W} \in \{0,1,2,\dots,W\}$ .

我们如果把上述问题们的当前最优解记作 $dp_{\mathscr{W}}$ ，那么这些最优解就又满足最优子结构了：当考虑到第 $i$ 个物品时，对于所有 $\mathscr{W}-w_i \ge 0$ 的 $dp_{\mathscr{W}}$ ，它的最优解只会来自于 $dp_{\mathscr{W}-w_i}$ ，写成状态转移方程就是 $dp_{\mathscr{W}}\gets \max\{dp_{\mathscr{W}},dp_{\mathscr{W}-w_i}+v_i\},\ \text{st.}\ \mathscr{W}-w_i \ge 0$ .

特别地， $dp_0\equiv 0$ .

最终，我们就可以递推出答案 $dp_W$ ，复杂度 $O(nW)$ .

这个划分过程实际上就是选择状态空间的过程，而其中遵循的原则就是：维护每个问题的最优解，但是为了保证最优解能够由先前的最优解转移过来，我们不能过多地“聚合”最优解，而是要适当地划分出多个问题，分别维护。

换一种理解方式，我们要求我们划分出的每个问题 $\mathscr{W}$ ，必须把后续决策所需的一切必要依据都显式地表达在 $\mathscr{W}$ 中。在背包问题中，后续的决策就是「能否从该最优解转移过来」，而决定这个的关键就是容量叠加是否超过上限，而通过编码 $\mathscr{W}$ ，决策的条件已经全部编码在了 $\mathscr{W}$ 中，不会出现先前的 $ans$ 方案中，最优解可能可以从 $ans_{i-1}$ 转移也可能无法从 $ans_{i-1}$ 转移的叠加态。

这种划分问题的方式，使得仅根据问题就能确定转移是否合法，而每个问题内部的选择无关紧要，就是无后效性。

更进一步#

刚刚以多项式复杂度解决了 0-1 背包问题，但是本题并不是经典的 0-1 背包，而是物品之间有依赖关系的背包。

分组背包#

由于每个主件最多只有 $2$ 个附件，因此每个主件最多可以派生出 $4$ 中组合方式——仅主件，主件和附件 $1$ ，主件和附件 $2$ ，主件和附件 $1$ 和 $2$ . 这个优化是本题特供的，也是解决本题至关重要的。

如果对每个主件，我们将上述 $4$ 中组合方式的价值和代价都提前算出，相当于把一个主件和它的所有附件转化为了 $4$ 件新的“物品”。这 $4$ 件物品作为一组，总共有 $O(n)$ 组，而题目的限制就转化为了在这 $O(n)$ 组中，每组至多选择一件物品。

于是我们成功把本题这个有依赖关系的背包转化为了一个分组背包问题，这也是很常见的背包问题类型。

分组背包要如何体现“每组”只能选择一个呢？只需要修改一下状态转移方程，变为：

遍历到第 $i$ 组时，设第 $i$ 组第 $j$ 个物品的代价和价值为 $w_{ij}$ 和 $v_{ij}$ .

dp_{\mathscr{W}}\gets \max\{dp_{\mathscr{W}}, \max_{j, \mathscr{W}-w_{ij} \ge 0}\{dp_{\mathscr{W}-w_{ij}}+v_{ij}\}\}

请注意，等号右侧的 $dp_{\mathscr{W}-w_{ij}}$ 是考虑前 $i-1$ 个物品时的解，左边的则是待更新的考虑前 $i$ 个物品时的解。但是，如果从小到大遍历 $\mathscr{W}$ ，那么右侧的 $dp_{\mathscr{W}-w_{ij}}$ 会被提前刷新为新的解，在更大的 $\mathscr{W}$ 时会获取到错误的值。因此，正确的方法是 $\mathscr{W}$ 从 $W$ 到 $1$ ，当然也可以增加一个临时数组存放结果，或者给 $dp$ 增加一个 $i$ 维度。

一些细节#

从本题的输入数据转化为分组背包，还是有一定难度的。具体方式可以见代码。注意主件可能在附件之后出现。

代码#

#include <bits/stdc++.h>
using namespace std;

const int P = 5, M = 70, N = 32010;

int n,m,mm;
struct Raw // 用于处理附件先于主件出现的情况
{
    int x,y,z;
}att[N];
int cnta;
struct Item // 每一组中的一个物品
{
    int p,v; // price value
};
struct Series // 一个组
{
    Item it[P];
    Item&operator[](const int&i){return it[i];}
}a[M];
int cnt[M]; // 某一组有几个物品，本题最多 4 个
int dp[N]; // 分组背包

int main()
{
    cin>>n>>m;
    for(int i=1,x,y,z;i<=m;i++)
    {
        cin>>x>>y>>z;
        if(!z)a[i][++cnt[i]]={x,x*y}; // 如果是主件，就直接成为第 i 组的第 1 个物品
        else att[++cnta]={x,y,z}; // 如果是附件，就缓存起来
    }
    for(int i=1;i<=cnta;i++) // 每个附件，对应到其主件所在组
    {
        a[att[i].z][++cnt[att[i].z]]={att[i].x,att[i].x*att[i].y};
    }
    mm=1;
    for(int i=1;i<=m;i++) // 由于附件对应位置的组是空的，我们可以做一个压缩，把所有组压缩到 1~mm 的下标位置
    {
        if(!cnt[i])continue;
        while(mm<i&&cnt[mm])mm++;
        swap(a[i],a[mm]);
        swap(cnt[i],cnt[mm]);
    }
    for(int i=1;i<=mm;i++) // 为每个组派生出至多 4 种组合方式
    {
        if(cnt[i]>=3)
        {
            a[i][++cnt[i]]={a[i][1].p+a[i][2].p+a[i][3].p, a[i][1].v+a[i][2].v+a[i][3].v};
        }
        for(int j=2;j<=min(3,cnt[i]);j++)
        {
            a[i][j].p+=a[i][1].p;
            a[i][j].v+=a[i][1].v;
        }
    }
    for(int i=1;i<=mm;i++) // 分组背包核心
    {
        for(int j=n;j>=1;j--)
        {
            for(int k=1;k<=cnt[i];k++)
            {
                if(j-a[i][k].p<0)continue;
                dp[j]=max(dp[j],dp[j-a[i][k].p]+a[i][k].v);
            }
        }
    }
    cout<<dp[n];
    return 0;
}

cpp