金明的预算方案

GitHub跳转原题关系图返回列表

把主件与它的至多两个附件组成家族，家族内枚举全部合法买法压成选项，家族间做一维倒序的分组背包，在预算内最大化价格与重要度乘积之和。

OJ: roj

题目 ID: 3549

难度:普及+/提高-

标签:动态规划背包分组背包python

创建: 2026-10-02 06:56

更新: 2026-10-10 11:30

前置题目

roj 1266【例9.10】机器分配B 把 A 教的「组内枚举选项、组间互斥」的分组背包转移整套搬到家族上：A 的第 i 组枚举 k 台对应 B 的组内枚举买法，B 的 dp[j]=max(dp[j],dp[j-cost]+gain) 就是这条转移的一维倒序版，B 额外叠加的流程（先在家族内部枚举买法消掉主件-附件依赖）是 A 没教的、也是它更难的部分。luogu P1734最大约数和B 的一维 knapsack 沿用 A 教的「倒序枚举容量保证每个数字只参与一轮转移」这一具体判定，只是把单个物品换成家族买法选项，使同组方案不被叠加、每组至多选一个；B 在此台阶上再叠加家族内枚举消依赖的新流程。roj 3141数字组合A 讲透的一维滚动倒序枚举（使 dp[j-cost] 仍是上一轮旧值、每件物品至多选一次）被 B 的分组背包原样复用：B 用同一个倒序容量循环保证同一家族的两个选项不会被叠加、每组至多选一种买法。

后置题目

luogu P5322[BJOI2019] 排兵布阵B 的主解（main.cpp：先 ndp = dp 冻结上一组状态，再对每个台阶用 dp[money-cost] 转移）复用了 A 教的「一维容量倒序/旧状态转移做分组背包、每组至多选一个选项」这一步，只是把家族买法换成排序合并得到的阈值台阶，并叠加阈值建模 luogu P5365英雄联盟B 的 main.cpp 先把 dp 备份成 ndp、再对每个英雄用 x 从旧状态 dp[cost] 转移，正是 A 教的『组内选项只能从上一组状态转移、不能叠加』这一步；A 靠容量倒序保证，B 换成 ndp 备份保证，只是把累加收益改成乘法收益并叠加阈值截断。luogu P2014[CTSC1997] 选课A 教的「依赖先在家族内枚举压成组内选项、再用一维倒序容量在互斥组间做分组背包（每组至多选一个）」正是 B 树形背包合并每棵孩子子树时实际使用的步骤：B 把每个孩子子树当成一组、名额 j 倒序转移 dp[u][j-k]+dp[v][k]（main.cpp 的 for (j=m+1;j>=1;j--)），只是在其上叠加虚拟根 0 把森林变树与子树状态 dp[u][j] 的定义。

形式化题目

给定总钱数 $N$ 与 $m$ 件物品。物品分主件与附件两类：每个主件可以有 0、1 或 2 个附件，附件不再有属于自己的附件；购买任何一件附件之前，必须先购买它所属的主件。第 $j$ 件物品有价格 $v_j$ （10 的整数倍）和重要度 $p_j \in [1, 5]$ 。

求一个总花费 $\leqslant N$ 的合法购买方案，使每件物品的 $v \times p$ 之和最大，即最大化

\sum_{j \in S} v_j \times p_j.

样例输入 $N = 1000,\ m = 5$ ：

物品	价格 $v$	重要度 $p$	归属	$v \times p$
1	800	2	主件	1600
2	400	5	附件 $\to$ 物品 1	2000
3	300	5	附件 $\to$ 物品 1	1500
4	400	3	主件	1200
5	500	2	主件	1000

物品 1、2、3 因依赖关系绑在一起：买 2 或 3 就必须买 1。样例的最优解是购买物品 4 和 5，总花费 $400 + 500 = 900 \leqslant 1000$ ，总收益 $1200 + 1000 = 2200$ （只买物品 1 收益 1600，物品 1 加物品 4 要 1200 元超预算），输出 2200。

正解

思路

朴素做法及其瓶颈。 最直接的两个念头都不行：

枚举全部 $2^m$ 个物品子集，逐个过滤依赖与预算—— $m < 60$ ，指数级不可接受；
把每件物品当成独立物品直接做 0-1 背包——花费、收益维度都对，但依赖被丢掉了，会选出"只买物品 2、3 不买物品 1"的非法方案；若给状态补上"哪些主件已买"，维度又是指数级。

可见瓶颈只有一处："买附件必须先买主件"这条依赖。再看依赖的形状——附件只依赖自己的主件，主件与主件之间、家族与家族之间没有任何依赖。于是把每个主件和它的至多两个附件看成一个家族：

家族内部最多 3 件物品，"主件必买、附件逐件决定买不买"的合法买法恰好只有 $2^a \leqslant 4$ 种；
每种买法都可以把多件物品压成一个复合选项（总花费 $c$ ，总收益 $s$ ）——依赖关系被枚举方式天然满足，不必再进状态；
各家族之间只剩"至多选一种买法（或整组不买）"的互斥选择。

这正是分组背包：第 $i$ 组是第 $i$ 个家族，组内选项是它的各种买法，容量是预算。

样例的分组与选项。 家族 A 有 2 个附件，共 4 种买法；B、C 没有附件，各 1 种：

家族	买法	花费 $c$	收益 $s$
A（物品 1、2、3）	只买主件 1	800	1600
A	主件 1 + 物品 2	1200	3600
A	主件 1 + 物品 3	1100	3100
A	主件 1 + 物品 2、3	1500	5100
B（物品 4）	只买主件 4	400	1200
C（物品 5）	只买主件 5	500	1000

转移设计。 设 $dp[j]$ 表示：已处理的家族在总花费不超过 $j$ 时的最大收益。逐组转移

dp[j] = \max\Big(dp[j],\ \max_{(c,\,s) \in \text{本组}} \{\, dp[j - c] + s \mid c \leqslant j \,\}\Big).

下表展示样例按 A → B → C 逐组处理后，几个关键容量上的 $dp$ 值：

处理到	$j=400$	$j=500$	$j=800$	$j=900$	$j=1000$
初始（一个家族都没选）	0	0	0	0	0
家族 A	0	0	1600	1600	1600
家族 B	1200	1200	1600	1600	1600
家族 C	1200	1200	1600	2200	2200

这张表有两个观察重点。其一，A 组最便宜的买法要 800 元，所以 $j < 800$ 时 A 行全为 0；B 组把 $j=400$ 填成 1200，但在 $j=800 \sim 1000$ 上被 A 的 1600 压住——这说明每个容量都要在"不选本组"和"选本组各选项"之间取最大，不能贪心。其二，C 行在 $j=900$ 处得到 $dp[400] + 1000 = 1200 + 1000 = 2200$ ，用的正是"处理完 B、还没处理 C"时的 $dp[400]$ ——即 B+C 的组合。要保证这一点，容量必须从 $N$ 倒序遍历：更新 $dp[900]$ 时下标 400 尚未被本轮改写， $dp[400]$ 仍是上一组结束后的值；同理，同组两个选项也绝不会被叠加进同一个解。最终 $\max_j dp[j] = 2200$ 。

代码

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-10 11:30
 * update_at: 2026-10-10 11:30
 */
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

struct Item { int v, p, q; };
Item items[65];

// 组：主件 (v, v*p) 在首位，其后是附件
vector<vector<pair<int, int> > > groups;
vector<pair<int, int> > opts[65];   // 每组的全部购买方案

// 生成一组的所有方案（必含主件，附件任选子集）
void build_options(int gi) {
    vector<pair<int, int> >& g = groups[gi];
    int main_v = g[0].first, main_s = g[0].second;
    int na = (int)g.size() - 1;
    opts[gi].clear();
    // 枚举附件子集
    for (int mask = 0; mask < (1 << na); mask++) {
        int cost = main_v, gain = main_s;
        for (int i = 0; i < na; i++)
            if (mask & (1 << i)) {
                cost += g[1 + i].first;
                gain += g[1 + i].second;
            }
        opts[gi].push_back(make_pair(cost, gain));
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int budget, m;
    cin >> budget >> m;
    for (int i = 1; i <= m; i++)
        cin >> items[i].v >> items[i].p >> items[i].q;

    // 分组：主件自开一组，附件挂到 q 指向的主件组尾
    int group_id[65];
    memset(group_id, 0, sizeof(group_id));
    for (int i = 1; i <= m; i++) {
        if (items[i].q == 0) {
            group_id[i] = (int)groups.size();
            groups.push_back(vector<pair<int, int> >());
            groups.back().push_back(make_pair(items[i].v, items[i].v * items[i].p));
        }
    }
    for (int i = 1; i <= m; i++) {
        if (items[i].q != 0) {
            int gid = group_id[items[i].q];
            groups[gid].push_back(make_pair(items[i].v, items[i].v * items[i].p));
        }
    }
    int G = (int)groups.size();
    for (int i = 0; i < G; i++) build_options(i);

    // 分组背包
    vector<int> dp(budget + 1, 0);
    for (int i = 0; i < G; i++) {
        for (int j = budget; j >= 0; j--) {
            for (size_t k = 0; k < opts[i].size(); k++) {
                int cost = opts[i][k].first, gain = opts[i][k].second;
                if (cost <= j && dp[j - cost] + gain > dp[j])
                    dp[j] = dp[j - cost] + gain;
            }
        }
    }
    int ans = 0;
    for (int j = 0; j <= budget; j++) ans = max(ans, dp[j]);
    cout << ans << "\n";
    return 0;
}

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-10-02 07:06
# update_at: 2026-10-02 07:06

import sys
from itertools import combinations

Item = tuple[int, int, int]   # (价格, 重要度, 归属主件编号，0 表示自己是主件)
Group = list[tuple[int, int]]  # 组首是主件 (价格, 价格x重要度)，其后是它的附件


def build_groups(items: list[Item]) -> list[Group]:
    """把物品按主件分组：主件自开一组，附件挂到 q 指向的主件组尾。"""
    groups: list[Group] = []
    slot: dict[int, Group] = {}  # 主件编号 -> 它的组，附件按 q 查表
    for i, (v, p, q) in enumerate(items, 1):  # 物品编号 1..m，附件的 q 必指向更靠前的主件
        if q == 0:
            slot[i] = [(v, v * p)]
            groups.append(slot[i])
        else:
            slot[q].append((v, v * p))
    return groups


def group_options(group: Group) -> list[tuple[int, int]]:
    """主件组的全部购买方案 (花费, 收益)：必含主件，附件任选子集，不含"整组不买"。"""
    main_v, main_s = group[0]
    atts = group[1:]
    return [
        (main_v + sum(v for v, _ in combo), main_s + sum(s for _, s in combo))  # 一个方案
        for r in range(len(atts) + 1)            # 选 r 个附件，r=0 即只买主件
        for combo in combinations(atts, r)
    ]


def knapsack(plans: list[list[tuple[int, int]]], budget: int) -> int:
    """分组背包：每组至多选一个方案，返回不超过预算的最大收益。"""
    dp = [0] * (budget + 1)
    for opts in plans:
        # 容量倒序遍历：dp[j-cost] 还停在上一组的结果，同组的方案不会被叠加
        for j in range(budget, -1, -1):
            for cost, gain in opts:
                if cost <= j:
                    dp[j] = max(dp[j], dp[j - cost] + gain)
    return max(dp)


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    budget, m = next(data), next(data)  # 总钱数、物品件数
    items = [(next(data), next(data), next(data)) for _ in range(m)]
    plans = [group_options(group) for group in build_groups(items)]
    print(knapsack(plans, budget))


if __name__ == "__main__":
    solve()

build_groups 按 q 完成分组（附件的 q 必指向更靠前的主件，顺序读入即可挂到组尾）；group_options 用 combinations 枚举"主件 + 附件子集"的全部买法；knapsack 是标准的一维分组背包，倒序容量那行注释就是互斥性的来源。

复杂度

时间：设家族数 $g \leqslant m$ ，每组选项数 $\leqslant 4$ ，转移共 $O(g \times N \times 4) = O(mN)$ 次内层比较，数值上不超过 $60 \times 32000 \times 4 \approx 7.7 \times 10^6$ ，与标准 C++ 分组背包解法同阶；分组与生成选项均为 $O(m)$ 。
空间：一维 dp 数组 $O(N)$ （ $N < 32000$ ），分组与选项 $O(m)$ ，远低于 32MB 内存限制。

总结

本题的依赖"买附件必买主件"看起来像树形依赖，但由于深度只有 1 层、每主件至多 2 个附件，依赖被完全限制在家族内部。解法的核心动作是先在家族内部用枚举把依赖消掉——每个合法买法压成一个 (花费, 收益) 选项——再把家族之间的互斥选择交给分组背包的一维倒序转移。倒序容量是"每组至多选一个"的全部秘密：它让转移永远只读到上一组的结果。

金明的预算方案

目录

形式化题目

正解

思路

代码

复杂度

总结