题解：P12136 [蓝桥杯 2025 省 B] 生产车间

· · 题解

树上背包做法

题意

删除一些节点，使得剩余的所有节点正常工作，且根节点的单位时间打包数最大。

初看会想到 01 背包模型，即每个节点尽量在不超过自身权值的情况下，尽可能将多的权值装入背包。

但是，并非背包价值越大越好，从整体来看，子节点背包价值越高，父节点背包容量反而可能装不下如此大的价值，造成父节点背包价值并非最优解的情况。

因此，与其求出每个节点背包的最大价值，不如找到该节点背包价值的所有可能（在不超过自身权值的情况下）。

分析

题目要求删除一些节点，反过来想就是问我们保留哪些节点，即选择某些节点加入背包。
以叶子节点举例：

可以看到 A 作为叶子节点，只能提供 8（选）或 0（不选），同理，B 能提供 5 或 0，C 能提供 4 或 0，而他们的父节点 D 只能接收这三个孩子节点提供的权值，且权重之和不能超过自身的 10。

显而易见，这是一个分组背包的模型：A 分组中的值为 \left\{ 0,8 \right\}，B 分组中的值为 \left\{ 0,5 \right\}，C 分组中的值为 \left\{ 0,4 \right\}。对于每一分组，我们只能选择分组中的一个值放入背包。

每一个非叶子节点都有一个背包，而我们要求的是这个节点放入孩子节点提供的权值后，能产生的所有容量的可能。

比如：D 节点能产生背包容量的可能为 \left\{ 0,8,5,4,9 \right\}。

更详细的，我们以下图举例，其中 \left\{ \right\} 内容为该节点背包价值的所有可能，对于其父级来说就是分组背包中的“分组”。

状态转移方程

状态方程：

\text{dp}[i][j] = \begin{cases} 1, & \text{前}\space j \space\text{组能够产生}\space i\space\text{价值} \\ 0, & \text{前}\space j\space\text{组不能产生}\space i\space\text{价值} \end{cases}

转移方程：

\text{dp}[i][j] = \bigvee_{k=0}^{m_{j}} (i - v[j][k] \geq 0 \wedge \text{dp}[i - v[j][k]][j-1])

注：v[j] 表示第 j 分组，m_{j} 表示 j 分组内元素个数。

优化建议

求解背包问题部分可以用滚动数组降维，以达到优化空间复杂度的作用（但是给的空间够用就不管了）。

如果有别的优化建议欢迎评论区讨论！

易错点

如果你的代码只能通过大部分后面的测试点，而在前面测试点 WA 了，可以考虑数据输入的问题。

具体来讲，输入边的时候并没有指定谁是父节点，谁是子节点！

AC 代码

#include <bits/stdc++.h>
#include <iostream>
#include <string.h>
using namespace std;
// 树上背包

int w[1005],N,ans=0;
vector<vector<int>> cap(1005,vector<int> ()); //每个节点背包价值的所有可能
vector<vector<int>> adj(1005,vector<int> ()); //邻接表

int work(int u)
{
    if(adj[u].size()==0) //如果当前节点是叶子节点
    {
        cap[u].push_back(w[u]);
        return cap[u].size();
    }
    // 若不是叶子节点
    vector<vector<bool>> dp(1005,vector<bool> (1005,0)); //dp数组
    dp[0][0]=1;
    for(int i=0;i<=w[u];i++)
        for(int j=1;j<=adj[u].size();j++)
        {
            if(i==0) dp[i][j]=1; //价值为0一定可以成立
            else if(dp[i][j-1]) dp[i][j]=1; //此组之前已经满足了i，直接转移
            else
            {   
                int v=adj[u][j-1],len;
                if(cap[v].size()==0) len=work(v); //递归调用
                else len=cap[v].size();
                for(int k=0;k<len;k++)
                    if(i-cap[v][k]>=0 && dp[i-cap[v][k]][j-1]) //转移方程
                        {dp[i][j]=1; break;}
            }
            if(j==adj[u].size() && dp[i][j]) cap[u].push_back(i); //遍历到行末再加入分组，防止重复加入
        }

    return cap[u].size(); //返回分组内元素个数
}

int main()
{
    cin>>N;
    for(int i=1;i<=N;i++)
        cin>>w[i];
    for(int i=1;i<=N-1;i++)
    {
        int u,v; cin>>u>>v;
        if(u>v) swap(u,v);
        adj[u].push_back(v);
    }

    work(1);
    for(int i=0;i<cap[1].size();i++)
        ans=max(ans,cap[1][i]); //找根节点背包价值的最大可能
    cout<<ans;  

    system("pause");
    return 0;
}