笔记汇总

有依赖背包问题 实质上是在每个子树上求 分组背包。

我们通常做的 背包问题 都是 线性结构，但 有依赖背包问题 是一个 树形结构。

先比较一下以往 线性背包DP 的 状态转移，第 $i$ 件 物品 只会依赖第 $i−1$ 件 物品 的状态

如果本题我们也采用该种 状态依赖关系 的话，对于节点 $i$，我们需要枚举他所有 子节点 的组合 $2^k$ 种可能

想到我们上次所说的 背包DP的原理 了吗，我们不需要枚举完这 $2^k$ 中不同选法。

而是利用 值域很小 这一特点来重叠 子结构，

放到这里，就是枚举每个 状态 分给各个子节点 的 体积。

因为 上层子树 是 下层子树 的 前提条件，不能 不满足条件却有结论，

所以我们不应该先枚举 上层子节点的状态，所以我们应该 由下往上 枚举，先计算 子节点的状态。

在枚举的时候，我们要为被搜索到的结点 留位置，不然其子树的 所有状态 都不满足。

时间复杂度 $O(N×V×V)$

void dfs(int u)
{
    //先枚举所有状态体积小于等于j-v[u]的所有子节点们能够获得的最大价值
    for (int i = h[u]; ~i; i = ne[i])
    {
        int son = e[i];
        dfs(son); //从下往上算，先计算子节点的状态
        for (int j = m - v[u]; j >= 0; -- j) //枚举所有要被更新的状态
        {
            for (int k = 0; k <= j; ++ k)   //枚举该子节点在体积j下能使用的所有可能体积数
            {
                f[u][j] = max(f[u][j], f[u][j - k] + f[son][k]);
            }
        }
    }
    //最后选上第u件物品
    for (int j = m; j >= v[u]; -- j) f[u][j] = f[u][j - v[u]] + w[u];
    for (int j = 0; j <  v[u]; ++ j) f[u][j] = 0;   //清空没选上u的所有状态
}

时间复杂度 $O(N×2^N×V)$

void dp(int u, int j)
{
    int siz = aff[u].size();
    //二进制枚举，列举出所有的分组背包内的物品
    for (int st = 0; st < 1 << siz; ++ st)
    {
        int v_sum = v[u], w_sum = w[u];//必须购买主键后，附件才有价值
        for (int i = 0; i < siz; ++ i)
        {
            if (st >> i & 1)
            {
                v_sum += v[aff[u][i]];
                w_sum += w[aff[u][i]];
            }
        }
        //状态转移
        if (v_sum <= j) f[j] = max(f[j], f[j - v_sum] + w_sum);
    }
}

int main()
{
    //input
    cin >> m >> n;
    for (int i = 1; i <= n; ++ i)
    {
        int fa;
        cin >> v[i] >> w[i] >> fa;
        w[i] *= v[i];
        if (fa) aff[fa].push_back(i);
        else not_aff[i] = true;//标记分组背包的物品组
    }
    //dp
    for (int i = 1; i <= n; ++ i)
        if (not_aff[i]) //分组背包
            for (int j = m; j >= 0; -- j)
                dp(i, j);
    //output
    cout << f[m] << endl;
    return 0;
}