传送门：P1064 [NOIP 2006 提高组] 金明的预算方案

更佳的阅读体验：洛谷 P1064 题解

简要题意：共有 $n$ 元钱和 $m$ 个物品，每个物品有价格 $v$ 和重要度 $w$。物品分为主件和附件，每个主件拥有 $0 \sim 2$ 个附件，购买附件时必须同时购买主件。设计一个购买方案，使得所有物品的价格与重要度的乘积总和（即 $\sum \limits_{i = 1}^{m} v_i \times w_i$）最大，并输出这个总和。

如果我们将每件物品的单价看作体积，价格与重要度的乘积看作价值，共有 $n$ 元钱看作最大容积，那么可以发现这是一个 0-1 背包问题。但是似乎与朴素的 0-1 背包不太一样，因为有主件与附件之分。

因为如果要买附件，就一定要买它对应的主件，也就是说，不会存在单独购买附件的情况。同时，附件不再有从属于自己的附件，那么当购买主件和某些附件时，我们就可以将主件与附件视作一个整体。

此时问题就变得简单起来。我们仍然可以套用 0-1 背包的模板，只需要多加几次状态转移即可，用来判断应该只购买主件、购买主件和其中一个附件，还是购买主件和它的两个附件。

为了方便转移，我们需要提前对每个附件进行预处理。把存储每个物品的价格 $v$ 和重要度 $w$ 的数组开成二维数组，$v_{i, 0}$ 与 $p_{i, 0}$ 表示物品 $i$ 的价格和重要度，$v_{i, 1}$ 和 $p_{i, 1}$ 表示物品 $i$ 的第 $1$ 个附件的价格和重要度，$v_{i, 2}$ 和 $p_{i, 2}$ 表示物品 $i$ 的第 $2$ 个附件的价格和重要度。

#include <iostream>
using namespace std;
using ll = long long;

const int N = 3.2e4 + 10, M = 70, P = 4;
int n, m, x, y, z, v[M][P], p[M][P], f[N];

int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    cin >> n >> m;
    for (int i = 1; i <= m; ++i) {
        cin >> x >> y >> z;
        if (!z) v[i][0] = x, p[i][0] = y;
        else if (!v[z][1]) v[z][1] = x, p[z][1] = y;
        else v[z][2] = x, p[z][2] = y;
    } for (int i = 1; i <= m; ++i)
        for (int j = n; j; --j) {
            if (v[i][0] <= j) f[j] = max(f[j], f[j - v[i][0]] + v[i][0] * p[i][0]);
            if (v[i][0] + v[i][1] <= j)
                f[j] = max(f[j], f[j - v[i][0] - v[i][1]] + v[i][0] * p[i][0] + v[i][1] * p[i][1]);
            if (v[i][0] + v[i][2] <= j)
                f[j] = max(f[j], f[j - v[i][0] - v[i][2]] + v[i][0] * p[i][0] + v[i][2] * p[i][2]);
            if (v[i][0] + v[i][1] + v[i][2] <= j)
                f[j] = max(f[j], f[j - v[i][0] - v[i][1] - v[i][2]] + v[i][0] * p[i][0] + v[i][1] * p[i][1] + v[i][2] * p[i][2]);
        }
    cout << f[n] << '\n';
    return 0;
}