有依赖的背包

一、例题：金明的预算方案

有若干件物品，分为主件和附件。购买附件之前，必须购买它所属的主件。每件物品只能购买一次，第 $i$ 件物品的价格为 $v_i$，重要度为 $p_i$，购买它得到的价值为 $v_i\times p_i$，即价格乘以重要度。

在总花费不超过预算的情况下，求能够获得的最大总价值。

例题：LG1180 金明的预算方案。本题每个主件最多有两个附件，附件不会再有附件。

二、枚举主件和附件的组合

考虑一个主件及它的附件。如果不买主件，那么它的附件也不能买；如果买主件，可以选择购买其中的部分附件。

当主件 $A$ 有两个附件 $B,C$ 时，合法选择只有：

把每个主件及其附件看成一组，组内的每种购买组合看成一件“新物品”。每组最多选择一种组合，因此转化为分组背包。

每个主件至多有两个附件，购买主件后只有 $2^2=4$ 种附件选择，枚举这些组合是可行的。

三、分组背包转移

设 dp[j] 表示处理过的主件组中，总花费不超过 $j$ 的最大总价值。

对每个主件，按照以下顺序枚举预算和合法组合，并用组合的总花费、总价值进行转移：

枚举主件 → 倒序枚举预算 → 枚举当前主件的组合

进行转移。每个预算用 best 暂存本组所有选择的最大值，组内枚举结束后再写回 dp[j]。

本题允许物品价格为 $0$，组合花费也可能为 $0$。使用 best 可以保证这一组的所有组合都从处理本组之前的状态转移，避免在同一组中重复选取。初始 dp[] 全为 $0$，表示可以不购买任何物品。

四、参考代码

输入第一行为预算 $n$ 和物品数 $m$。接下来每行输入 $v_i,p_i,q_i$；$q_i=0$ 表示主件，否则 $q_i$ 是所属主件的编号。主件可能出现在附件之后，因此先读入所有物品，再统一处理。

#include <iostream>
#include <algorithm>
using namespace std;

const int M = 65;
const int N = 32005;
int v[M], p[M], q[M];
int attachment[M][2], cnt[M];
int dp[N];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= m; ++i) {
        cin >> v[i] >> p[i] >> q[i];
        if (q[i] != 0) {
            attachment[q[i]][cnt[q[i]]++] = i;
        }
    }

    for (int i = 1; i <= m; ++i) {
        if (q[i] != 0) continue;  // 只处理主件

        int a = attachment[i][0];  // 不存在的附件编号为 0
        int b = attachment[i][1];
        for (int j = n; j >= 0; --j) {
            int best = dp[j];  // 不购买这个主件
            // 只购买主件
            if (j >= v[i]) {
                best = max(best, dp[j - v[i]] + v[i] * p[i]);
            }
            // 购买主件和附件 a
            if (a && j >= v[i] + v[a]) {
                best = max(best, dp[j - v[i] - v[a]] + v[i] * p[i] + v[a] * p[a]);
            }
            // 购买主件和附件 b
            if (b && j >= v[i] + v[b]) {
                best = max(best, dp[j - v[i] - v[b]] + v[i] * p[i] + v[b] * p[b]);
            }
            // 购买主件和两个附件
            if (a && b && j >= v[i] + v[a] + v[b]) {
                best = max(best, dp[j - v[i] - v[a] - v[b]] + v[i] * p[i] + v[a] * p[a] + v[b] * p[b]);
            }
            dp[j] = best;
        }
    }

    cout << dp[n] << '\n';
    return 0;
}

本题 $n\le32000$、$m\le60$，每组最多枚举 $4$ 种购买主件的组合。时间复杂度为 $O(mn)$，空间复杂度为 $O(m+n)$。

五、依赖关系更复杂时

如果一个主件有 $k$ 个附件，直接枚举购买组合需要考虑 $2^k$ 种情况；当 $k$ 较大时，这种方法就不适用了。此时可以在选定主件后，对附件逐个做 01 背包，避免枚举所有子集。

如果附件还可以拥有自己的附件，依赖关系形成一棵树或森林：选择一个节点，必须先选择它的父节点。这时可以使用树形背包：先求出每个子树内部的 DP，再将子树的状态逐个合并到父节点。多棵树可以增加一个不占费用、不产生价值的虚拟根来统一处理。

树形背包需要结合树形 DP 学习，具体转移与实现放在树形 DP 章节介绍。