题解 | #【模板】有依赖的背包问题#

题目链接

题目描述

现有 $N$ 朵云（物品），编号为 $1, \dots, N$ 。每朵云 $i$ 都有一个价格 $c_i$ 和一个价值 $v_i$ 。

存在 $M$ 个搭配关系。每个搭配关系连接两朵云 $u$ 和 $v$ ，表示购买 $u$ 就必须购买 $v$ ，反之亦然。这种关系是传递的，例如，如果 $u$ 与 $v$ 搭配， $v$ 与 $z$ 搭配，那么购买这三者中的任意一个，都必须同时购买另外两个。

你现在有 $W$ 的钱，目标是最大化你能购买到的云的总价值。

解题思路

这道题目是经典的 分组背包 问题，其核心思想是 并查集 和 0/1背包 的结合。

1. 物品分组

题目中的“搭配关系”具有对称性和传递性。这意味着所有相互关联的物品形成了一个个独立的集合（或组）。对于每个组内的物品，我们的决策是捆绑的：要么购买整个组的所有物品，要么一个都不买。

这种集合划分的问题，正是并查集（Disjoint Set Union, DSU）擅长解决的。我们可以将每朵云看作一个节点，每个搭配关系看作一条边。

初始化：创建 $N$ 个集合，每个集合只包含一朵云。
合并：遍历 $M$ 个搭配关系 $(u, v)$ ，调用并查集的 unite(u, v) 操作，将 $u$ 和 $v$ 所在的集合合并。

完成所有合并操作后，所有云朵就被划分成了若干个独立的组。

2. 计算每组的总成本和总价值

在物品分组之后，我们需要将每个组视为一个“超级物品”。这个超级物品的成本是组内所有云朵的价格之和，其价值也是组内所有云朵的价值之和。

我们可以遍历所有云朵 $i=1, \dots, N$ ：

找到云朵 $i$ 所在组的根节点 root = find(i)。
将云朵 $i$ 的价格 $c_i$ 累加到根节点 root 对应的总价格上。
将云朵 $i$ 的价值 $v_i$ 累加到根节点 root 对应的总价值上。

这样，我们就得到了一系列新的物品（组），每个物品都有一个总成本和总价值。

3. 0/1背包求解

现在问题转化为了一个标准的0/1背包问题：

背包容量： $W$
物品：上一步中计算出的每个“超级物品”（组）
目标：在不超过背包容量的前提下，选择若干物品，使得总价值最大。

我们可以使用动态规划来解决。定义 $dp[j]$ 表示花费不超过 $j$ 的钱所能获得的最大价值。

状态转移方程为： $dp[j] = \max(dp[j], dp[j - \text{group\_cost}] + \text{group\_value})$

其中 group_cost 和 group_value 是当前正在考虑的组的总成本和总价值。

为了确保每个组（物品）只被选择一次，我们需要在内层循环中逆序遍历背包容量，即从 $W$ 到 group_cost。

最终的答案就是 $dp[W]$ 。

代码

c++
java
python

#include <iostream>
#include <vector>
#include <numeric>

using namespace std;

struct Item {
    int cost;
    int value;
};

vector<int> parent;

int find_root(int i) {
    if (parent[i] == i) {
        return i;
    }
    return parent[i] = find_root(parent[i]);
}

void unite_sets(int a, int b) {
    int root_a = find_root(a);
    int root_b = find_root(b);
    if (root_a != root_b) {
        parent[root_b] = root_a;
    }
}

int main() {
    int n, m, w;
    cin >> n >> m >> w;

    vector<Item> items(n + 1);
    for (int i = 1; i <= n; ++i) {
        cin >> items[i].cost >> items[i].value;
    }

    parent.resize(n + 1);
    iota(parent.begin(), parent.end(), 0);

    for (int i = 0; i < m; ++i) {
        int u, v;
        cin >> u >> v;
        unite_sets(u, v);
    }

    vector<Item> groups(n + 1, {0, 0});
    for (int i = 1; i <= n; ++i) {
        int root = find_root(i);
        groups[root].cost += items[i].cost;
        groups[root].value += items[i].value;
    }

    vector<long long> dp(w + 1, 0);
    for (int i = 1; i <= n; ++i) {
        // 只处理作为根节点的组
        if (parent[i] == i) {
            for (int j = w; j >= groups[i].cost; --j) {
                dp[j] = max(dp[j], dp[j - groups[i].cost] + groups[i].value);
            }
        }
    }

    cout << dp[w] << endl;

    return 0;
}

import java.util.Scanner;

class Item {
    int cost;
    int value;

    public Item(int cost, int value) {
        this.cost = cost;
        this.value = value;
    }
}

public class Main {
    private static int[] parent;

    public static int findRoot(int i) {
        if (parent[i] == i) {
            return i;
        }
        return parent[i] = findRoot(parent[i]);
    }

    public static void uniteSets(int a, int b) {
        int rootA = findRoot(a);
        int rootB = findRoot(b);
        if (rootA != rootB) {
            parent[rootB] = rootA;
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        int w = sc.nextInt();

        Item[] items = new Item[n + 1];
        for (int i = 1; i <= n; i++) {
            items[i] = new Item(sc.nextInt(), sc.nextInt());
        }

        parent = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            parent[i] = i;
        }

        for (int i = 0; i < m; i++) {
            int u = sc.nextInt();
            int v = sc.nextInt();
            uniteSets(u, v);
        }

        Item[] groups = new Item[n + 1];
        for (int i = 0; i <= n; i++) {
            groups[i] = new Item(0, 0);
        }

        for (int i = 1; i <= n; i++) {
            int root = findRoot(i);
            groups[root].cost += items[i].cost;
            groups[root].value += items[i].value;
        }

        long[] dp = new long[w + 1];
        for (int i = 1; i <= n; i++) {
            if (parent[i] == i) { // 是一个组的根节点
                for (int j = w; j >= groups[i].cost; j--) {
                    dp[j] = Math.max(dp[j], dp[j - groups[i].cost] + groups[i].value);
                }
            }
        }

        System.out.println(dp[w]);
    }
}

import sys

# 增加递归深度
sys.setrecursionlimit(200005)

def find_root(i):
    if parent[i] == i:
        return i
    parent[i] = find_root(parent[i])
    return parent[i]

def unite_sets(a, b):
    root_a = find_root(a)
    root_b = find_root(b)
    if root_a != root_b:
        parent[root_b] = root_a

def main():
    n, m, w = map(int, sys.stdin.readline().split())

    items = [[0, 0] for _ in range(n + 1)]
    for i in range(1, n + 1):
        items[i] = list(map(int, sys.stdin.readline().split()))

    global parent
    parent = list(range(n + 1))

    for _ in range(m):
        u, v = map(int, sys.stdin.readline().split())
        unite_sets(u, v)

    groups = [[0, 0] for _ in range(n + 1)]
    for i in range(1, n + 1):
        root = find_root(i)
        groups[root][0] += items[i][0]  # cost
        groups[root][1] += items[i][1]  # value

    dp = [0] * (w + 1)
    for i in range(1, n + 1):
        if parent[i] == i:  # 是一个组的根
            cost = groups[i][0]
            value = groups[i][1]
            for j in range(w, cost - 1, -1):
                dp[j] = max(dp[j], dp[j - cost] + value)
    
    print(dp[w])

if __name__ == "__main__":
    main()

算法及复杂度

算法：并查集 + 0/1背包动态规划
时间复杂度： $\mathcal{O}(N \cdot W + M \cdot \alpha(N))$ 。其中，并查集构建分组的时间约为 $\mathcal{O}(M \cdot \alpha(N))$ ，聚合组信息的时间为 $\mathcal{O}(N \cdot \alpha(N))$ 。0/1背包部分，最多有 $N$ 个组，背包容量为 $W$ ，时间复杂度为 $\mathcal{O}(N \cdot W)$ 。因此总时间复杂度由背包部分主导。
空间复杂度： $\mathcal{O}(N + W)$ 。并查集和分组信息需要 $\mathcal{O}(N)$ 的空间，DP数组需要 $\mathcal{O}(W)$ 的空间。