A背包 DP

有依赖的背包

主件-附件·依赖→分组

本课摘要

有依赖的背包课程回答“带主件附件依赖的选择怎样转化为合法组合”。内容以主件-附件·依赖→分组为主线，配合逐步推导、可编辑演示、例题与练习形成可复查的学习闭环。

  • 判断有依赖的背包的适用条件与状态边界
  • 围绕“主件-附件·依赖→分组”推导转移与计算顺序
  • 用演示、复杂度分析和配套题目校验实现
本课目录 · 0 节

正在整理目录…

当「选它」得先「选它的主件」

先看一个具体场景：有一件主件 (w,v)=(2,3)(w,v)=(2,3)，还有它的两件附件， 附件 1 (2,4)(2,4)、附件 2 (3,5)(3,5)，一个容量 W=7W=7 的背包。规则多了一条硬约束：附件必须依附主件而选，想装附件 1，就必须先把主件也装上；主件不装，两个附件都是非法的。目标仍是不超重下让总价值最大。

主件w=2v=3附件 1w=2v=4附件 2w=3v=5虚线 = 依赖：选附件，必先选它指向的主件
1 个主件 + 2 个附件：虚线是「依赖」，附件指向主件，选附件的前提是先选主件。

很自然会想：把主件、附件 1、附件 2 当成三件独立的 01 物品丢进背包不就行了？不行。普通 01 背包会毫不客气地只挑附件 1、不挑主件（附件 1 性价比高），可这在依赖规则里是非法的，它压根不知道「附件得先有主件」这回事。 反过来，也没法用「先强制装主件再随便挑附件」蒙混：主件到底装不装、装了之后还剩多少钱给附件，本身就是要一起权衡的决策。

那把「主件带哪些附件」的所有情形枚举出来呢？主件要么不装；一旦装，它的两个附件各可带可不带，仅主 / 主+附1 / 主+附2 / 主+附1+2，加上「整个不装」，就把这一族物品的合法方案全数罗列了。这份枚举，正是打开依赖背包的钥匙。

归约：把「主 + 附件子集」打包成组

盯住上面那句枚举。一个主件带上它附件的某个子集，就构成一个合法组合；每个组合的费用 = 主件费用 + 所选附件费用之和，价值 = 各自价值之和。 本例主件 (2,3)(2,3) 配两个附件，附件子集有 22=42^2=4 种，于是得到 4 个组合：

同一组 · 至多选一个组合仅主费用 2价值 3主+附1费用 4价值 7主+附2费用 5价值 8主+附1+2费用 7价值 12
主件 + 附件子集枚举成 4 个组合：仅主(2,3)、主+附1(4,7)、主+附2(5,8)、主+附1+2(7,12)。它们归为同一组，组内至多选一个。

关键的一跃在这里：这 4 个组合互斥，你不可能同时「只带附件 1」又「两个附件都带」，一个主件最终只能落实成其中一种方案（或整个不选）。这正是分组背包的定义：把这些组合归为同一组，组内至多选一个。

于是有依赖的背包，被归约成了分组背包，一个主件（连同它的附件）= 一组，组内物品 = 该主件的各个合法组合。为什么必须走这条「枚举组合」的路、而不能把附件当独立物品？因为独立物品会漏掉「选附件必先选主件」这条约束；而把主件焊进每个组合里，就让「带附件」永远伴随「带主件」，约束天然成立。

状态与转移：落到分组背包

既然归约成了分组背包，转移就直接套分组背包那一套。设 f[j]f[j] 为花费不超过 jj 时的最大价值，逐个主件（每个当一组）更新。 处理某个主件这一组时，一格 f[j]f[j] 有两条来路：

这一组 · 容量 jf[j] = ?不选本组选组内某个组合这个主件一带都不要= f_old[j]枚举组合 c，取 max= f_old[j−w_c] + v_c取较大者 = max(两者)组内各组合都基于「本组未出手」的旧值 → 至多选一个组合 = 一个合法方案
每格 f[j] 两条路：不选本组(这个主件一带都不要)，或在组内枚举某个组合 c 取 max。两条路都基于本组处理前的旧值。

不选本组：这个主件连同附件一概不要，价值就是处理本组之前的 f[j]f[j]。

选组内某个组合 cc（费用 wcw_c、价值 vcv_c，需 j≥wcj\ge w_c）：腾出 wcw_c，剩下的 j−wcj-w_c 交给之前的最优，再加上 vcv_c。究竟选哪个组合？把每个组合都试一遍取最好。合起来就是分组背包的转移：

f[j]=max⁡(f[j], max⁡c ∈ G, wc≤j(f[j−wc]+vc))f[j]=\max\Big(f[j],\ \max_{c\,\in\,G,\ w_c\le j}\big(f[j-w_c]+v_c\big)\Big)

一维写法照分组背包：外层枚举主件（组）、中层容量 jj 倒序、内层枚举本组的各个组合。容量倒序保证组内各组合都基于「本组尚未出手」的旧值，一组至多落实一个组合，正好对应「一个主件最终只有一种方案」。

本质

有依赖的背包 = 分组背包的一个实例。诀窍全在建组：把「一个主件 + 它附件的任一子集」枚举成组内物品，用「组合恒含主件」把「选附件必先选主件」这条依赖，化进了物品的定义里。归约完成后，转移与循环顺序一字不差地照搬分组背包。

跟着算一遍

用本例（主件 (2,3)(2,3)、附件 (2,4)(2,4) 与 (3,5)(3,5)，容量 7）走一遍，重点盯住枚举组合 → 组内取一个：

0
枚举组合。 主件配两个附件，得 4 个组合：仅主 (2,3)(2,3)、主+附1 (4,7)(4,7)、主+附2 (5,8)(5,8)、主+附1+2 (7,12)(7,12)。四者归为同一组，至多选一个。
1
地基。 处理这一组之前，任何容量下 f[j]=0f[j]=0（什么都还没装）。
2
看容量 4。 装得下的组合有「仅主」(2,3)(2,3) 与「主+附1」(4,7)(4,7)：分别 = f[4−2]+3=3f[4-2]+3=3、f[4−4]+7=7f[4-4]+7=7。取较大 → f[4]=7f[4]=7（主+附1）。
3
看容量 7（读答案）。 四个组合都装得下，其中「主+附1+2」(7,12)(7,12) 给出 f[7−7]+12=12f[7-7]+12=12，压过其余。f[7]=12f[7]=12，正是主件带上两个附件全装，价值 3+4+5=123+4+5=12，恰好占满容量 7。
下面的演示会先亮出 4 个组合的（费用, 价值），再把这一组的分组转移逐格跑一遍。改主件或附件的 w,vw,v、改容量，看组合与表格实时重算。

看它把依赖枚成组、再逐格转移

主件（必选前提）· 可改 w / v
主件 w
2
主件 v
3
附件（依主件而选）· 可改 w / v
附1
w
2
v
4
附2
w
3
v
5
背包容量
W
7
枚举出的 4 个组合（同一组，至多选一个）：仅主: (w=2, v=3)主+附1: (w=4, v=7)主+附2: (w=5, v=8)主+附12: (w=7, v=12)
0
1
2
3
4
5
6
7
∅
这组
0
0
0
0
0
0
0
0
·
·
·
·
·
·
·
·
当前计算 依赖来源 被选转移 已确定
22=42^{2} = 4
第一步：枚举组合。附件必须依主件而选，所以每个合法组合都含主件，再叠加附件的一个子集，共 4 个：仅主(2,3)，主+附1(4,7)，主+附2(5,8)，主+附12(7,12)。它们构成同一组，组内至多选一个，问题就归约成了分组背包。
已暂停，第 1 步，共 11 步，1 倍速

深化：附件多了、依赖连成了树

本例每个主件只挂 2 个附件，枚举 22=42^2=4 个组合毫无压力。P1064 正是这种「主件 + 至多 2 附件」的教科书原型，每个主件最多 4 个组合，直接枚举即可。 但依赖可以更深：如果附件本身又能挂自己的附件，依赖关系就从「主-附两层」长成了一棵树（甚至一片森林）。

P2014 选课就是这样：一门课可能有先修课，要选它必先选先修，先修关系把课程连成树。这时「枚举一个节点的所有后代子集」会指数爆炸，不能再照搬本页的暴力枚举，而要在树上做 DP：f[u][j]f[u][j] 表示以 uu 为根的子树、选课数（或容量）为 jj 时的最优，把子树当分组、在各子树间做背包合并。

承接：依赖成树 → 树上背包

「主件-附件」是依赖背包最浅的两层形态，归约成分组背包即可解。当依赖连成树/森林（如 P2014 选课的先修关系），它一般化为树上背包（树形 DP），那是F 部分的主题。本页只点到「依赖成树」这一形态，树形转移的细节留到那里展开。

例题

P1064[NOIP2006 提高组] 金明的预算方案NOIP2006 提高组提高+/省选-
题意
总钱数 nn，mm 件物品，每件给出价格 vv、重要度 p(1∼5)p(1\sim5)、以及归属 qq（q=0q=0 为主件，否则表示它是第 qq 号主件的附件）。每个主件至多 2 个附件，选附件必先选其主件。求 ∑v×p\sum v\times p 的最大值。
对应关系
「价格」= 费用 ww，「v×pv\times p」= 价值，「总钱数 nn」= 容量。每个主件 = 一组，枚举 仅主 / 主+附1 / 主+附2 / 主+附1+2 四种组合作为组内物品，依赖背包归约成分组背包的教科书原型。
转移 · 复杂度
f[j]=max⁡(f[j], f[j−wc]+vc)f[j]=\max(f[j],\ f[j-w_c]+v_c)，外层枚举主件、中层 jj 倒序、内层枚举本主件的组合（至多 4 个）；时间 O(nm)O(nm) 级。
参考代码（枚举组合的分组背包）
C++
在洛谷打开 P1064 
#include <iostream>
#include <algorithm>
using namespace std;

int mw[65], mv[65];             // 主件的费用、价值(=价格×重要度)
int aw[65][3], av[65][3];       // 每个主件的附件(至多 2 个)：费用、价值
int cnt[65];                    // 每个主件挂了几个附件
long long f[32005];             // f[j]：花费不超过 j 时的最大 价格×重要度 之和

int main()
{
    int n, m;
    cin >> n >> m;              // n=总钱数，m=物品数
    for (int i = 1; i <= m; i++)
    {
        int v, p, q;
        cin >> v >> p >> q;     // v=价格, p=重要度(1~5), q=0 主件 / 否则=所属主件编号
        if (q == 0)             // 是主件
        {
            mw[i] = v;
            mv[i] = v * p;
        }
        else                    // 是附件，挂到主件 q 上
        {
            aw[q][cnt[q]] = v;
            av[q][cnt[q]] = v * p;
            cnt[q]++;
        }
    }

    for (int i = 1; i <= m; i++)    // 逐个主件，当作「一组」
    {
        if (mw[i] == 0) continue;   // i 不是主件(是附件或不存在)，跳过
        for (int j = n; j >= mw[i]; j--)    // ★倒序：组内至多选一个组合
        {
            // 枚举本主件的合法组合(含主件)，对附件的每个子集取一遍
            for (int s = 0; s < (1 << cnt[i]); s++)
            {
                int w = mw[i], val = mv[i];         // 组合恒含主件
                for (int k = 0; k < cnt[i]; k++)
                    if (s >> k & 1)                 // 该附件入选
                    {
                        w += aw[i][k];
                        val += av[i][k];
                    }
                if (j >= w)
                    f[j] = max(f[j], f[j - w] + val);
            }
        }
    }

    cout << f[n] << endl;
    return 0;
}
P2014[CTSC1997] 选课CTSC1997（洛谷原生 P）提高+/省选-
题意
nn 门课，每门有学分，部分课有唯一先修课（选它必先选先修）。先修关系把课程连成森林。选 mm 门课，求最大学分和。
为什么选它（依赖的一般化）
它把依赖从「主件-附件两层」推广到树/森林：附件还能有自己的附件。此时不能再暴力枚举子集，而要在树上做 DP，每棵子树当一组，在子树间做背包合并。是从「依赖背包」跨到「树上背包」的桥梁题。
思路（只点到「依赖成树」）
建虚根 00 把森林并成一棵树，选课总数 mm 相应 +1+1。树形背包 f[u][j]f[u][j] = 子树 uu 选 jj 门的最大学分，逐棵子树做分组合并。本页不展开树形转移细节，完整做法见 F 部分 · 树上背包。

练习

说明：有依赖的背包原生题池很窄，几乎以 P1064（主件-附件两层）与 P2014（依赖成树）为双核。下面给两层依赖的 P1064 夯实归约；更一般的树上依赖（如 P2014 选课）在 F 部分树上背包展开，不在此重复。

P1064[NOIP2006 提高组] 金明的预算方案把每个主件枚举成 仅主 / 主+附1 / 主+附2 / 主+附1+2 四种组合，当作同一组的组内物品，做分组背包（外层主件、中层容量倒序、内层枚举组合）。价值用 价格×重要度。在洛谷打开
P2014[CTSC1997] 选课进阶：依赖连成森林。建虚根并成一棵树、m+1，做树上背包 f[u][j]（子树间分组合并）。属 F 部分树上背包，本页仅作承接，可先了解「依赖成树」的形态。在洛谷打开
依赖背包是分组背包的应用；当依赖长成树，它通向 F 部分的树上背包。两条线都从这页的「枚举组合」出发。

已进入 有依赖的背包 · 背包 DP · DP大师