有依赖的背包

1
2
3
4
5
6
7
8

7 10
2 3 0
3 4 1
4 5 1
1 2 0
2 6 4
3 3 4
1 1 0

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

// 有依赖的背包（简化版，NOIP2006 金明的预算方案）：每个主件最多 2 个附件
//
// 一个主件和它的附件，可能的买法是：不买、只买主件、主件+附件1、主件+附件2、
// 主件+两个附件 —— 至多 5 种，且互斥。所以「主件及其附件」等价于一个物品组，
// 用分组背包求解：容量倒序，组内枚举买法。
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e3 + 5;

int n, C;
int f[maxn];
int w[maxn], v[maxn];

int att1[maxn], att2[maxn];   // 每个主件的第 1、2 个附件的编号，0 表示没有

int main() {
    cin >> n >> C;

    int mainIdx[maxn], mainCnt = 0;
    for (int i = 1; i <= n; ++i) {
        int p;
        cin >> w[i] >> v[i] >> p;
        if (p == 0) mainIdx[++mainCnt] = i;
        else if (att1[p] == 0) att1[p] = i;
        else att2[p] = i;
    }

    for (int t = 1; t <= mainCnt; ++t) {
        int m = mainIdx[t];
        int c1 = att1[m], c2 = att2[m];

        // 先枚举容量（倒序），再枚举这一组的互斥买法
        for (int j = C; j >= 0; --j) {
            int best = f[j];                                   // 不买
            if (j >= w[m])                                     // 只买主件
                best = max(best, f[j - w[m]] + v[m]);
            if (c1 && j >= w[m] + w[c1])                       // 主件 + 附件1
                best = max(best, f[j - w[m] - w[c1]] + v[m] + v[c1]);
            if (c2 && j >= w[m] + w[c2])                       // 主件 + 附件2
                best = max(best, f[j - w[m] - w[c2]] + v[m] + v[c2]);
            if (c1 && c2 && j >= w[m] + w[c1] + w[c2])         // 主件 + 两个附件
                best = max(best, f[j - w[m] - w[c1] - w[c2]] + v[m] + v[c1] + v[c2]);
            f[j] = best;
        }
    }
    cout << f[C] << endl;
    return 0;
}

1

16

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

// 有依赖的背包：依赖关系是一棵森林，加虚拟根 0 变成一棵树
// 选了儿子就必须选父亲，所以对每个点 u：
//   1. 先把所有儿子的 dp 数组合并进来（每个儿子是一个「物品组」，至多选一个方案）
//   2. 再强制把 u 自己放进去（j >= w[u] 时才有值，否则无解）
// 儿子用链式前向星存，不依赖 STL 容器
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e3 + 5;
const int NEG = -1e9;

int n, C;
int w[maxn], v[maxn];
int f[maxn][maxn];      // f[u][j]：以 u 为根的子树，装了 u，花费 j 的最大价值

int head[maxn], nxt[maxn], to[maxn], ecnt;   // 链式前向星存儿子

void add(int p, int u) {                     // p 是父亲，u 是儿子
    to[++ecnt] = u; nxt[ecnt] = head[p]; head[p] = ecnt;
}

void dfs(int u) {
    // 先把 u 自己放进去：花费 w[u] 才有价值 v[u]
    for (int j = 0; j <= C; ++j)
        f[u][j] = (j >= w[u]) ? v[u] : NEG;

    for (int e = head[u]; e; e = nxt[e]) {
        int son = to[e];
        dfs(son);
        // 合并儿子：枚举分给「已合并部分」多少容量
        for (int j = C; j >= 0; --j) {
            for (int k = 0; k <= j; ++k) {
                if (f[u][j - k] == NEG || f[son][k] == NEG) continue;
                f[u][j] = max(f[u][j], f[u][j - k] + f[son][k]);
            }
        }
    }
}

int main() {
    cin >> n >> C;
    for (int i = 1; i <= n; ++i) {
        int p;
        cin >> w[i] >> v[i] >> p;
        add(p, i);                  // p=0 时自然挂到虚拟根 0 下
    }

    dfs(0);

    // 根 0 不占容量、不产生价值，答案就是 f[0][C]（可以什么都不选）
    cout << max(0, f[0][C]) << endl;
    return 0;
}

1

17