树形背包
Eva.Q Lv9
2022-07-02 13:55:44

“我们还有那么长的路要走。” 男孩叹了口气。

“是啊，但是你看，我们已经走了这么远了。” 马说。

背包

01 背包

有 个物品，每个物品只有一个，每个物体都有对应的体积和价值，求在总体积不超过 的前提下，最大化物品的价值和。

状态定义：f[i][j] 表示 前 个物品总体积不超过 时的最大收益。

转移方程：f[i][j] = max(f[i - 1][j], f[i - 1][j - v[i]] + w[i]) 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int f[1007][1007];
int v[1007], w[1007];

int main() {
    int n = rd(), m = rd();
    for (int i = 1; i <= n; ++i) {
        v[i] = rd(); w[i] = rd();
    }
    memset(f, 0, sizeof(f));
    for (int i = 1; i <= n; ++i) {
        for (int j = 0; j <= m; ++j) {
            if (j < v[i]) f[i][j] = f[i - 1] [j];
            else f[i][j] = max(f[i - 1][j], f[i - 1][j - v[i]] + w[i]);
        }
    }
    printf("%d\n", f[n][m]);
    return 0;
}

压缩空间

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int f[1007], v[1007], w[1007];

int main() {
    int n = rd(), m = rd();
    for (int i = 1; i <= n; ++i) {
        v[i] = rd(); w[i] = rd();
    }
    memset(f, 0, sizeof(f));
    for (int i = 1; i <= n; ++i) {
        for (int j = m; j >= 0; --j) {
            if (j < v[i]) f[j] = f[j];
            else f[j] = max(f[j], f[j - v[i]] + w[i]);
        }
    }
    printf("%d\n", f[m]);
    return 0;
}

完全背包

有 个物品，每个物品有无限个，每个物品有对应的体积和价值，求在总体积不超过 的前提下，最大化物品的价值和。

状态定义：f[i][j] 表示 前 个物品总体积为 时的最大收益。

转移方程：f[i][j] = max(f[i - 1][j], f[i][j - v[i]] + w[i]) 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int f[1007][1007], v[1007], w[1007];

int main() {
    int n = rd(), m = rd();
    for (int i = 1; i <= n; ++i) {
        v[i] = rd(); w[i] = rd();
    }
    memset(f, 0, sizeof(f));
    for (int i = 1; i <= n; ++i) {
        for (int j = 0; j <= m; ++j) {
            if (j < v[i]) f[i][j] = f[i - 1][j];
            else f[i][j] = max(f[i - 1][j], f[i][j - v[i]] + w[i]);
        }
    }
    printf("%d\n", f[n][m]);
    return 0;
}

压缩空间

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int f[1007], v[1007], w[1007];

int main() {
    int n = rd(), m = rd();
    for (int i = 1; i <= n; ++i) {
        v[i] = rd(); w[i] = rd();
    }
    memset(f, 0, sizeof(f));
    for (int i = 1; i <= n; ++i) {
        for (int j = 0; j <= m; ++j) {
            if (j < v[i]) f[j] = f[j];
            else f[j] = max(f[j], f[j - v[i]] + w[i]);
        }
    }
    printf("%d\n", f[m]);
    return 0;
}

树形背包

在一个树上，每一个结点都有一个价值和体积，求在总体积不超过 时，最大化物品的价值和。要求，如果要选某个点，该点的父节点一定要选。

设置状态：f[i][j] 表示，以 为根的子树中，体积不超过 时，能有的最大价值和。

模板：

不优化，复杂度为 

1
2
3
4
5
6
7
8
9
10
11
12
13
void dfs(int u， int fa) {
    for (auto son : e[u])
        if (son != fa) {
            dfs(son, u);
            for (int j = V; j >= 0; --j) // 给以u为根的子树多大体积 （不包含该儿子结点后面的儿子结点和u）
            	for (int k = 0; k <= j; ++j) // 给以son为根的子树多大体积
                    f[u][j] = max(f[u][j], f[u][j - k] + f[son][k]);
           	sum[u] += sum[son]
        }
    // 强制把根节点塞进去
    sum[u] += v[u];
    for (int j = min(V, sum[u]); j; --j) f[u][j] = f[u][j - v[u]] + w[u];
}

优化后，复杂度为 

1
2
3
4
5
6
7
8
9
10
11
12
13
void dfs(int u， int fa) {
    for (auto son : e[u])
        if (son != fa) {
            dfs(son, u);
            for (int j = min(V, sum[u] + sum[son]);j >= 0; --j) // 上界就是该儿子的子树的最大体积和在他前面的子树的最大体积的和
            	for (int k = max(0, j - sum[u]); k <= min(j, sum[son]); ++j) // 上界时不超过该儿子的子树的最大体积，下界表示能给当前子树的最小体积，就是前面的子树都塞满
                    f[u][j] = max(f[u][j], f[u][j - k] + f[son][k]);
           	sum[u] += sum[son]
        }
    // 强制把根节点塞进去
    sum[u] += v[u];
    for (int j = min(V, sum[u]); j; --j) f[u][j] = f[u][j - v[u]] + w[u];
}

洛谷P2014

有些课程有前置课程，如果要选这个课，就必须同时选他的前置课程。现要从所有的课里选 门，要最大化能获得的学分。

思路：这是一道模板题，数据范围不大，即使不优化也可以过。每门课的体积就是 ，价值就是学分。有一个问题就是，可能会有多棵树，我们建一个虚点 号点，其价值和代价都是 。使用优化的方法，代码如下。

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
#define N 307

int n, m, f[N][N], w[N], sum[N];

vector<int> son[N];

void dfs(int u) {
    for (auto v : son[u]) {
        dfs(v);
        for (int j = min(m, sum[u] + sum[v]); j >= 0; --j)
            for (int k = max(j - sum[u], 0); k <= min(j, sum[v]); ++k)
                f[u][j] = max(f[u][j], f[u][j - k] + f[v][k]);
        sum[u] += sum[v];
    }
    if (u) {
        sum[u]++;
        for (int j = min(m, sum[u]); j; --j) f[u][j] = f[u][j - 1] + w[u];
    }
}

int main() {
    n = rd(); m =rd();
    for (int i = 1; i <= n; ++i) {
        son[rd()].push_back(i);
        w[i] = rd();
    }
    dfs(0);
    int ans = 0;
    for (int i = 1; i <= m; ++i) ans = max(ans, f[0][i]);
    printf("%d\n", ans);
    return 0;
}

洛谷P2015

给一棵树，每条边有一个权值，求在只保留 条树枝的前提下，最大化所有保留下来的边的权值和。

思路：把边的权值当作在子结点上。然后就跟上一道题一样了。采用邻接表的方式存图，dfs 的时候，把权值作为参数传下去。

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
#define N 307

int n, Q, f[N][N], sum[N], tot, hd[N];

struct edge {int to, w, nxt;} e[N];

void add(int u, int v, int w) {
    e[++tot].to = v; e[tot].w = w;
    e[tot].nxt = hd[u]; hd[u] = tot;
}

void dfs(int u, int fa, int w) {
    for (int i = hd[u], v; i; i = e[i].nxt) {
        if ((v = e[i].to) != fa) {
            dfs(v, u, e[i].w);
            for (int j = min(Q, sum[u] + sum[v]); j >= 0; --j)
                for (int k = max(j - sum[u], 0); k <= min(j, sum[v]); ++k)
                    f[u][j] = max(f[u][j], f[u][j - k] + f[v][k]);
            sum[u] += sum[v];
        }
    }
    if (u) {
        sum[u]++;
        for (int j = min(Q, sum[u]); j; --j) f[u][j] = f[u][j - 1] + w;
    }
}

int main() {
    n = rd(); Q = rd();
    for (int i = 1; i < n; ++i) {
        int u = rd() - 1, v = rd() - 1, w = rd();
        add(u, v, w); add(v, u, w);
    }
    dfs(0, 0, 0);
    int ans = 0;
    for (int i = 1; i <= Q; ++i) ans = max(ans, f[0][i]);
    printf("%d\n", ans);
    return 0;
}

代码源219

给一棵以 号点为根的树，每个点有一个价值，相邻两个点不能同时选，最多选 个点，问最大的价值是多少。

思路：大体上跟上面的思路差不多，但其转移方程更像昨天学的树形DP。增加一维表示当前这个点选还是不选。

注意，枚举体积更新的时候，要倒着枚举

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
#define N 507

int n, m, f[N][N][2], w[N], sum[N];

vector<int> son[N];

void dfs(int u) {
    for (auto v : son[u]) {
        dfs(v);
        for (int j = min(m, sum[u] + sum[v]); j >= 0; --j)
            for (int k = max(j - sum[u], 0); k <= min(j, sum[v]); ++k) {
                f[u][j][0] = max(f[u][j][0], f[u][j - k][0] + max(f[v][k][0], f[v][k][1]));
                f[u][j][1] = max(f[u][j][1], f[u][j - k][1] + f[v][k][0]);
            }
        sum[u] += sum[v];
    }
    sum[u]++;
    for (int i = min(m, sum[u]); i; --i) f[u][i][1] = f[u][i - 1][1] + w[u];
}

int main() {
    n = rd(); m = rd();
    for (int i = 2; i <= n; ++i) son[rd()].push_back(i);
    for (int i = 1; i <= n; ++i) w[i] = rd();
    dfs(1);
    int ans = 0;
    for (int i = 1; i <= m; ++i) ans = max(ans, max(f[1][i][0], f[1][i][1]));
    printf("%d\n", ans);
    return 0;
}
  • Post title：树形背包
  • Post author：Eva.Q
  • Create time：2022-07-02 13:55:44
  • Post link：https://qyy/2022/07/02/Algorithm/knapsack-on-tree/
  • Copyright Notice：All articles in this blog are licensed under BY-NC-SA unless stating additionally.