详解泛化物品解决树形依赖背包问题

· · 个人记录

1 题目描述

有N个物品和一个容量是V的背包。

物品之间具有依赖关系，且依赖关系组成一棵树的形状。如果要选择一个物品放入背包，则必须先将它的父节点放入背包。每件物品的编号是i，体积是v_i，价值是 w_i，依赖的父节点编号是p_i（注：p_i为-1时表示节点i为根节点）。物品的下标范围是 1…N。

求解将哪些物品装入背包，可使物品总体积不超过背包容量，且总价值最大。

输出最大价值。

数据范围
1≤N,V≤1000 1≤v_i,w_i≤100

2 题目分析

2.1 泛化物品

定义：泛化物品可以视作一个价值随着体积变化的函数w_i=f(v_i)

例如：一个体积为2、价值为3的物品$A$，装入物品后的背包可以视为如下的一个泛化物品: $f(0)=0,f(1)=0,f(2)=3,f(3)=3,...,f(V)=3 $f(0)=0,f(1)=4,f(2)=4,f(3)=7,...,f(V)=7

2.2 带有依赖关系的泛化物品

$f(0)=0,f(1)=0,f(2)=3,f(3)=7,...f(V)=7 $\quad$ 很显然，如果所有物品的依赖关系最终是个线性结构，那么问题会非常好解决，但是若是**树形结构**该怎么解决呢？比如：再来一个物品$C$，且物品$C$依赖与物品$A$（即要想将物品$C$放入背包，必须先将物品$A$放入背包）。 $\quad$ 在徐持衡的论文里提到，可以考虑一下现有的泛化物品$f_2$与物品$C$如何进行合并，那么泛化物品的并到底是个什么意思呢？ --- ![图1](https://foruda.gitee.com/images/1692206768460600601/412bfc01_13319175.png) 图1 ------------ $\quad$ 首先，我们定义任一节点到根节点的路径，如图1所示，节点$C$的路径(记为$path_C$)为从$root$到节点$A$，然后直接到节点$C$，中间不经过任何其他多余的节点（比如节点$B$）。然后路径上各个节点的体积之和我们记为$sum$，比如节点$C$的我们记为$sum_C$。我们将背包的容积记为$V$。 $\quad$ 然后我们可以知道对于任何某个节点$X$，若其$sum_X > V$，则可以直接对其剪枝。也就是说，我们所有纳入考虑的节点所组成的树是原始输入的树的一部分，并且满足条件：其任意$path$的$sum$都不超过$V$。然后我们约定整篇文章考虑的就是这种修剪完的、满足这种条件的树。 $\quad$ 先明确每个节点的$f$数组的含义： - $f_s$的最终含义是：对于任何$v>=sum_s$的$f_s[v]$，$f_s[v]$代表在体积$v$里装入了$path_s$上的所有节点的条件下，继续考虑装入"以节点$s$为根的子树里的其他节点(也即排除子树的根节点$s$)"所能获得的最大值。(注意：节点$s$只可能影响最终结果里$v >= sum_s$的值，对于$v < sum_s$的值其实与节点$s$的父节点的$f$元素值一样。后面可以看到，我们最终的做法不会将父节点$f$数组里$v < sum_s$的元素值复制给$f_s$，因为没有必要) --- $\quad$ 那么我们最终的答案就是$ans[v]=max(f_0[v], f_{root}[v])$。其中，由于所有的方案可以分成两类：一类是不包含根节点的方案(实际上就是一个节点都不装入)，另一类是包含根节点的方案。我们用$f_0$数组代表前者，实际上它的所有元素值都是0。 $\quad$ 定义完了$f_s$的最终含义，我们再来看看$f_s$的未计算出最终结果时的中间状态的含义。节点$s$可能会被遍历许多次，每次遍历我们都会更新一次$f_s$数组(后面我们会看到，在从$s$的父节点首次进入节点$s$之前，我们会初始化$f_s$数组；在从节点$s$的孩子节点回溯到节点$s$时，我们会更新一次$f_s$数组)。**那么每次遍历更新后，$f_s$数组就代表：在当前遍历过的节点里挑选，并且必须装入$path_s$上的所有节点的条件下，所能取得的最大值**(这其实也是**这个问题的状态定义**)。 $\quad$ 这个描述一下子不太容易理解，我们举个例子（参照图2）来详细解释一下。我们假设当前此次遍历节点$s$时，是从节点$s$的第i个儿子节点$z_i$回溯回来的（对于节点$s$的儿子节点的编号，我们从左往右依次记为$z_1$，$z_2$，...，$z_i$，...，$z_n$）。当前未更新的节点$s$的数组代表的是泛化物品$g_1$，注意到圆圈内的红色箭头所组成的$path$，这表示$g_1$不是圆圈内所有物品对应的泛化物品，它还必须再满足一个额外的条件：对于$v >= sum_s$，$f_s[v]$里必须装有红色路径(也即$path_s$)上的所有节点，$g_2$也是同样的道理。另外，注意$g1$的范围是红色$path_s$左边的所有节点（包括红色$path_s$）。 $\quad$ 当前需要合并子树$z_i$（将以$z_i$为根的子树称作子树$z_i$），我们只需要对计算$max(f_s[v],f_{z_i}[v])$即可。其中$v >= sum_{z_i}$。那么为什么这样计算是正确的呢？ --- ![图2 树上泛化物品的并](https://foruda.gitee.com/images/1692256527870217946/2518a5ed_13319175.png) 图2 --- $\quad$ 不难发现，在从节点$z_i$回溯到节点$s$时，当前已遍历的节点集合(记为$S$)已经扩大了，多了子树$z_i$的节点。那么对于$v >= sum_{z_i}$时的$f_s[v]$和$f_{z_i}[v]$，$f_s[v]$对应的节点集合是绿色圆圈的范围，其方案都不包含节点$z_i$；而$f_{z_i}[v]$对应的则是橙色圆圈的范围，其方案都包含节点$z_i$。而这恰好不重不漏的分割了当前$S$集合里的所有方案。 $\quad$ 这样我们就只需要正确计算节点$z_i$的数组$f_{z_i}[]$即可。在从节点$s$进入节点$z_i$时，我们这样进行初始化：对于$v >= sum_{z_i}$，$f_{z_i}[v]=f_s[v-v[z_i]]+w[z_i]$，这相当于把节点$z_i$塞进背包，虽然可能会挤走一些物品，但是其对应的方案不是$[root,...,s,z_i]$,而是还可能含有子树$z_1$到子树$z_{i-1}$里的节点。 $\quad$ **综上所述，我们可以看到整个过程就是先将子节点与当前的泛化物品合并，将合并后的结果作为子节点对应的泛化物品；然后在回溯时，对父节点和子节点对应的两个泛化物品取并，不断重复这两种操作，直到回溯回到整棵树的根节点。** --- # 代码实现 ## 复杂度：时间复杂度$O(N * V)$,空间复杂度$O(N * V) 
import java.util.Scanner;
import java.io.BufferedInputStream;
import java.util.Arrays;

public class Main {
    static final int N = 110;
    static int[][] f;
    static int[] h, e, ne, v, w;
    static int idx, n, m;

    static{
        f = new int[N][N];
        h = new int[N];
        e = new int[N];
        ne = new int[N];
        v = new int[N];
        w = new int[N];

        Arrays.fill(h, -1);
    }

    public static void main(String[] args){
        Scanner sin = new Scanner(new BufferedInputStream(System.in));

        n = sin.nextInt();
        m = sin.nextInt();

        int root = -1;
        for(int i = 1; i <= n; i++){
            v[i] = sin.nextInt();
            w[i] = sin.nextInt();

            int p = sin.nextInt();
            if(p == -1) root = i;
            else insert(i, p);
        }

        for(int i = v[root]; i <= m; i++) f[root][i] = w[root];
        dfs(root, v[root]);

        System.out.println(f[root][m]);

        sin.close();
    }

    static void dfs(int root, int vsum){
        if(vsum > m) return;
        for(int i = h[root]; i != -1; i = ne[i]) {
            int son = e[i];

            // 初始化son的泛化物品数组，并且强制将son节点放入背包
            for(int j = vsum + v[son]; j <= m; j++){
                f[son][j] = f[root][j - v[son]] + w[son];
            }

            dfs(son, vsum + v[son]);

            for(int j = vsum + v[son]; j <= m; j++){
                f[root][j] = Math.max(f[root][j], f[son][j]);
            }
        }
    }

    static void insert(int number, int parent){
        e[idx] = number;
        ne[idx] = h[parent];
        h[parent] = idx++;
    }
}

参考文献

  1. 题解 P2014 【选课】
  2. 徐持衡 《浅谈几类背包问题》2008
  3. 【LuoguP1273有线电视网】树形依赖背包
  4. ZQC-树上背包
  5. 树形背包总结

  6. LibreOJ #160. 树形背包题解

    转载本文请注明出处