浅谈泛化物品——树上背包优化

· · 个人记录

泛化物品

泛化物品，是一种没有固定费用（体积）和价值的物品。物品的价值，随着你给它定的费用（体积）而改变。

在 0/1 背包中，我们定义的 dp 数组，就是一类泛化物品，因为 dp[j] 表示物品总体积为 j 时，能得到的最大价值。我们要想使物品总体积为 j，可以通过将不同的物体拼凑在一起使得总体积为 j。这多个泛化物品拼凑而成的，也是泛化物品。

泛化物品的和与并

设：背包最大体积为 m，f[j] 表示物体总体积为 j 时，能取得的价值。

则有 f[j]=f[j-k]+f[k],k\in [0,j],j\in [k,m]。

我们称这种运算为泛化物品的和，泛化物品的和是把两个泛化物品和合并成一个泛化物品的运算，即枚举对这两个泛化物品如何分配体积。

对于具有树形依赖关系的背包问题，我们可以将每一棵子树当成一个泛化物品，这样对于每一个子树，子树的根节点与根节点相连的所有子树的泛化物品的和就是该子树的泛化物品。时间复杂度 O(nm^2)，n 为物体的个数。

如 [HAOI2010]软件安装 

void dfs(int now){
    for(int i=0;i<=m;i++){
        if(new_w[now]<=i){
            dp[now][i]=new_v[now];
        }
        else
            dp[now][i]=-0x3f3f3f3f;
    }
    for(int i=new_head[now];i;i=new_edge[i].next){
        int to=new_edge[i].to;
        dfs(to);
        for(int j=m;j>=new_w[now];j--){
            for(int k=new_w[to];k<=j;k++){
                dp[now][j]=max(dp[now][j],dp[now][j-k]+dp[to][k]);
            }
        }
    }
}

时间复杂度为 O(m^2)。

但是在经典问题 0/1 背包中，求一个泛化物品与一个单独物品的复杂度仅为 O(m)。

这是因为在 $0/1$ 背包中，我们是将一个泛化物品和一个单独的确定了的物品来合成的。这时我们对 $dp[j]$ 和 $dp[j-w]$ 这两个泛化物品，并不是进行和运算，而是进行两个泛化物品的并运算。 如果两个泛化物品有交集，我们就不能对他们进行和运算，而是并运算。 即 $dp[j]=max(dp[j],dp[k])

时间复杂度 O(m)。

很显然，进行泛化物品的并运算，比泛化物品的和运算，时间复杂度要更优。

所以我们要对树上背包问题进行优化，可以从把和运算转化成并运算入手

树上背包问题优化

对于一个根节点 i，我们强制让它选择子节点 s，并让以 s 为根的子树用 i 选择了 s 以后的初始状态进行 dp，这样最后子树 s 表示的泛化物品和 i 表示的泛化物品，就有了交的关系，直接把 s,i 的泛化物品，通过并运算计算出答案，赋值给根节点 i 即可。

void dfs(int now,int sum){//sum记录还剩多少容量
    if(sum<=0)
        return ;
    for(int i=new_head[now];i;i=new_edge[i].next){
        int to=new_edge[i].to;
        for(int j=0;j<=sum-new_w[to];j++){//因为强制选了to，所以要给to留出空间
            dp[to][j]=dp[now][j];//强制选择to，
        }
        dfs(to,sum-new_w[to]);//选了to 容量减少
        for(int j=sum;j>=new_w[to];j--){
            dp[now][j]=max(dp[now][j],dp[to][j-new_w[to]]+new_v[to]);//跟0/1背包统计答案的方法一样，两个泛化物品的并运算
        }
    }
}

时间复杂度 O(nm)，至此，我们成功将树上背包问题从 O(nm^2) 优化至 O(nm)。

来源：2009年国家集训队论文集，浅谈背包问题