[NOIP 2006 提高组] 金明的预算方案

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

附件挂主件，对每个主件枚举附件组合(最多2^2种)，转成0/1背包做倒序转移。

OJ: luogu

题目 ID: P1064

难度:普及+/提高-

标签:动态规划01背包分组背包有依赖背包

日期: 2026-08-08 23:13

目录

  1. 题意
  2. 思路
  3. 代码
  4. 复杂度
  5. 总结

题意

有 mm 个物品，每个物品有价格 viv_i、重要度 wiw_i。物品分主件和附件，附件从属于某个主件。买附件前必须先买对应的主件。每个主件最多有 22 个附件。总预算 nn 元，求价格 ×× 重要度的总和的最大值。

1≤n≤3.2×1041\le n\le 3.2\times 10^4，1≤m≤601\le m\le 60。

思路

一句话本质：附件不能独立选，必须挂载到主件上。把每个主件及其附件看成一个小组合，枚举附件所有选法后每个组合成为一个 0/1 物品，做标准 0/1 背包。

每个物品不能独立选——先买附件必须买主件，这个约束怎样纳入背包模型？

如果把主件和附件拆开独立处理，就会面临"附件被选但主件没选"的非法状态。更自然的做法是把主件和它的附件捆绑处理：主件必须选，附件可选可不选。

一个主件最多有 2 个附件，这意味着有多少种选择组合？

主件本身有"选"和"不选"两种情况。如果选了主件，附件可以选 0 个、1 个或 2 个。两个附件各有选/不选两种状态，所以选了主件后附件有 2k2^k 种组合（kk 为附件数量，k≤2k\le 2）。

因此对每个主件 ii，可以枚举 mask 从 00 到 2k−12^{k}-1，mask 的二进制第 tt 位为 11 表示选第 tt 个附件。这个组合的总花费为：

cost=vi+∑t∈选中附件vattach[t]cost = v_i + \sum_{t\in\text{选中附件}} v_{attach[t]}

总价值为：

val=vi⋅wi+∑t∈选中附件vattach[t]⋅wattach[t]val = v_i\cdot w_i + \sum_{t\in\text{选中附件}} v_{attach[t]}\cdot w_{attach[t]}

得到组合后怎么关联到背包上？

每个主件对应一组互斥的选项（主件不选则是空组合，主件选则选一种附件组合）。对于同一主件的不同组合只能选一个——这其实就是分组背包。但因为这里每组只处理一个主件，直接在容量维倒序遍历，对每个容量尝试这组的所有组合即可：

dp[j]=max⁡(dp[j],  dp[j−cost]+val)dp[j] = \max(dp[j],\; dp[j-cost] + val)

外层遍历每个主件（跳过附件），内层容量 jj 从 nn 到 00 倒序，内内层枚举该主件的所有附件组合。

价格都是 1010 的整数倍，有用吗？

这是一个常规模优化：所有价格除以 1010 后 nn 变成 32003200，DP 数组缩小 1010 倍。不过本题 n=32000n=32000 不优化也够用。

代码

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

const int MAXN = 32005;

int n, m;
int v[65], p[65], q[65];       // 价格、重要度、主件编号
vector<int> attach[65];         // attach[i] 表示主件 i 的附件列表
// dp[j] 表示花费 j 元能获得的最大价值（价格 × 重要度）。
int dp[MAXN];

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

    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        cin >> v[i] >> p[i] >> q[i];
        if (q[i] != 0) {
            attach[q[i]].push_back(i); // 附件挂到对应主件下
        }
    }

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

        int sz = attach[i].size();
        // 枚举当前主件的所有附件组合（2^sz 种）
        for (int j = n; j >= 0; j--) {
            for (int mask = 0; mask < (1 << sz); mask++) {
                int cost = v[i];
                int val = v[i] * p[i];  // 主件必选
                bool ok = true;
                for (int k = 0; k < sz; k++) {
                    if (mask >> k & 1) {
                        int a = attach[i][k];
                        cost += v[a];
                        val += v[a] * p[a];
                    }
                }
                if (j >= cost) {
                    dp[j] = max(dp[j], dp[j - cost] + val);
                }
            }
        }
    }

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

复杂度

  • 物品数 m≤60m\le 60，每个主件最多 22 个附件 → 最多 44 种组合
  • 总时间复杂度：O(60×4×n)≈O(240n)O(60 \times 4 \times n) \approx O(240n)
  • 空间复杂度：O(n)O(n)

总结

有依赖背包的核心是把"主件→附件"的依赖关系转化为组合枚举。因为附件数量小（≤2\le 2），枚举所有附件组合是可行的。如果附件更多则要用树形 DP。本题也是 NOIP 2006 提高组原题，是依赖背包的标准入门题。