分组背包时间优化

· · 个人记录

起源是一个讲师分析- P3177 [HAOI2015] 树上染色 中的树形动规时间复杂度

提示：可以先不看提到的具体题目, 先通篇浏览一下我的研究思路和结果

用子树大小来限制背包容量的遍历已经是公认的了,但是那天下午的模拟赛杀出了一道时间卡到离谱的问题

给定n个节点编号为1~n，每个节点有可能有一个父亲节点。

每个节点有一个价值v[i]，你需要从中选取m个节点，
这m个节点必须满足“如果某个点被选择，那么其父亲节点也要被选择”。

求m个节点总价值的最大值是多少。

试图用子树大小来限制只是无用的挣扎

void dfs(int u, int remain)
{
    if (remain == 0)
    {
        tree_size[u] = 0;
        return ;
    }   

    int accu = 1;   //已参与过dp的节点数量
    dp[u][1] = value[u];
    for (int e = V[u]; ~e; e = E[e].nexte)
    {
        int v = E[e].to;
        dfs(v, remain-1);
        for (int vol = min(accu, remain-1); vol >= 1; vol --)
            for (int w = min(tree_size[v], remain-vol); w >= 1; w --)
                dp[u][vol+w] = max(dp[u][vol+w], dp[v][w] + dp[u][vol]);
        accu += tree_size[v];   //该子树参与过dp了
    }
    tree_size[u] = accu;
}

(声明: remain代表最大容量, con代表目标容量, vol代表另一容量, w代表物品大小. con = vol + w)

上面代码的迷之优化有2处：

  1. 分组背包部分的遍历顺序改了, 状态转移方程变形了
  2. 一边dp一边记录用accu记录已参与过dp的节点数量, 并且用它来限制vol的最大值

图1代表常规分组背包的遍历顺序, 只注重外层的倒序。

图2代表改变后的遍历顺序, 内外层都递减(注意外层循环的变量的意义变了), 也能保证组内不堆叠。

如果二者都没有用优化2, 那时间复杂度都是O(remain×tree_size)。但是当二者都加上优化2时，就是上图中的情形: 内层的w循环一样, 但是外层con的循环比vol的循环更大, 二者差了一个present(当前子树的大小)

优化2不管遍历顺序怎样都能优化, 意义大概是使更新发生在信息集中的before区域。尤其在子树大小与remain相差较大, accu增长较缓时, 优化效果最为明显。但是我不清楚具体的复杂度。

优化2可以用在任何分组背包问题中, 但是优化1要看情况

于是我拿hdu的一道纯分组背包 ACboy needs your help 试试是否能迁移类似的优化, 先测试优化1

for (int i = 1; i <= n; i ++)
    for (int vol = m; vol >= 0; j --)
        for (int w = m-vol; w >= 0; w --)
            dp[vol+w] = max(dp[vol+w], dp[vol] + profit[i][w]);

统计核心dp语句的执行次数测试效率, 结果恰恰相反, 优化后执行次数反而变多？因为此题中每一组的物品最大都是全局最大容量(题面中的M), 优化1没有任何节省的空间, 但是复杂度还是一样的, 执行次数稍微增多只是一些边界问题

然后我试图加入优化2, 于是自己构造了一道题, 基于上一题多了一个限制: 每种课程不再都有k天, 而是各有各的, 参差不齐。用组内物品数量 代替 子树节点个数。

int accu = 0;
for (int i = 1; i <= n; i ++)
{
    for (int vol = min(accu, m); vol >= 0; vol --)
        for (int w = min(max_cost[i], m-vol); w >= 0; w --)
            dp[vol+w] = max(dp[vol+w], dp[vol] + profit[i][w]);

    accu += max_cost[i];
}

在这种情景下, 优化1在优化2的配合下才凸显出来

给一组典型数据

5 15
5 5 10 10 10 10 
5 2 6 6 8 10 
2 8 10 
2 1 8 
5 6 9 10 10 10

全局最大容量15较各组最大物品有一定差距, 在遍历各组时accu增长缓慢

当然优化2可以配合常规分组背包

int accu = 0;
for (int i = 1; i <= n; i ++)
{
    accu += max_cost[i];

    for (int con = min(accu, m); con >= 1; con --)
        for (int w = min(max_cost[i], con); w >= 1; w --)
            dp[con] = max(dp[con], dp[con-k] + profit[i][k]);
}

稍微思考就发现只要把 accu += max_cost[i] 语句提到dp计算前就行

总结

  1. 优化2可以优化所有分组背包问题
  2. 在各组最大物品与全局最大容量相差较多时, accu增长缓慢, 优化1在优化2的配合下凸显