hihoCoder题目赏析：刷油漆

本文来赏析hihoCoder上的一道题目“刷油漆”。为了解决这个题目，本文首先介绍了0-1背包和完全背包问题，它们在动态规划系列问题中是比较基础和典型的。然后本文在这两个问题的基础上，介绍了“刷油漆”问题的思路，并引入了一种名为“树形DP”的方法。

一、题目描述

1.1 背景故事

小Ho有着一棵灰常好玩的树玩具！这棵树玩具是由N个小球和N-1根木棍拼凑而成，这N个小球都被小Ho标上了不同的数字，并且这些数字都是处于1..N的范围之内，每根木棍都连接着两个不同的小球，并且保证任意两个小球间都不存在两条不同的路径可以互相到达。
小Ho的树玩具的质量似乎不是很好，短短玩了几个星期，便掉漆了！
“简直是一场噩梦！”小Ho拿着树玩具眼含热泪道。
“这有什么好忧伤的，自己买点油漆刷一刷不就行了？”小Hi表示不能理解。
“还可以这样？”小Ho顿时兴高采烈了起来，立马跑出去买回来了油漆。
但是小Ho身上的钱却不够——于是他只买回了有限的油漆，这些油漆最多能给M个结点涂上颜色，这就意味着小Ho不能够将他心爱的树玩具中的每一个结点都涂上油漆！小Ho低头思索了半天——他既不想只选一部分结点补漆，也不想找小Hi借钱，但是很快，他想出了一个非常棒的主意：将包含1号结点的一部分连通的结点进行涂漆（这里的连通指的是这一些涂漆的结点可以互相到达并且不会经过没有涂漆的结点），然后将剩下的结点拆掉！
那么究竟选择哪些结点进行涂漆呢？小Ho想了想给每个结点都评上了分——他希望最后留下来，也就是涂漆了的那些结点的评分之和可以尽可能的高！小Ho该如何做呢？

1.2 输入与输出

输入的第一行为两个整数N、M，意义如前文所述。
输入的第二行为N个整数，其中第i个整数Vi表示标号为i的结点的评分。
输入的第3~N+1行，每行分别描述一根木棍，其中第i+1行为两个整数Ai、Bi，表示第i根木棍连接的两个小球的编号。
要求输出一个整数，表示使得涂漆结点的评分之和最高可能是多少。

样例输入与输出
样例输入	样例输出
`10 4 370 328 750 930 604 732 159 167 945 210 1 2 2 3 1 4 1 5 4 6 4 7 4 8 6 9 5 10`	`2977`

二、引子一：0-1背包

背包问题是很基础也很典型的动态规划问题，是每个学习动态规划的人无法绕过的。背包问题指的是在给定N件物品（编号为1..N）、每件物品的价值value[i]以及每件物品的体积need[i]的前提下，计算可以放入总体积为M的背包中的物品的最大价值的问题。而背包问题根据同一物体最多只能选择一次还是可以选择任意多次，又分为0-1背包问题和完全背包问题两类，这一部分主要讨论0-1背包问题。
我们令F(i,j)表示选择前i件物品且背包剩余体积为j的情况下，可以达到的最大价值。为了计算F(i,j)，我们需要考虑两种情况：第一种情况是如果背包剩余体积j大于第i件物品的体积need[i]，我们可以选择第i件物品，这样我们只有j-need[i]的体积来容纳前i-1件物品，此时的价值为F(i-1,j-need[i])+value[i]；第二种情况是我们没有选择第i件物品，这样我们仍然有j的体积来容纳前i-1件物品，此时的价值为F(i-1,j)。F(i,j)为上述两个表达式中值较大的一个。F(N,M)即为我们要求的最终结果。
该算法的时间和空间复杂度是O(N*M)，因为需要生成一张N*M大小的表格并且将其填满。但是我们可以采取一些手段节省空间，通过状态转移方程，我们发现F(i,j)的值只与表格上一行的内容有关。所以我们可以只存储i和i-1两行，这样可以使空间复杂度减少至O(M)。

0-1背包

int main(){
    int objectCount, totalCapacity;
    cin >> objectCount >> totalCapacity;
    vector<int> need(objectCount);
    vector<int> value(objectCount);
    for(int i=0; i<objectCount; i++)
        cin >> need[i] >> value[i];

    //Dynamic programming:
    vector<int> table[2];
    table[0] = vector<int>(totalCapacity+1, 0);
    table[1] = vector<int>(totalCapacity+1);
    bool curTable = false; //curTable为true代表当前计算的是table[1]，否则代表当前计算的是table[0]。
    for(int i=0; i<objectCount; i++){
        curTable = !curTable;
        for(int j=1; j<=totalCapacity; j++){
            if(j >= need[i])
                table[curTable][j] = max(table[!curTable][j-need[i]] + value[i], table[!curTable][j]);
            else
                table[curTable][j] = table[!curTable][j];
        }
    }
    cout << table[curTable][totalCapacity];
    return 0;
}

补充：动态规划问题的两种性质

重复子问题：就像递归一样，计算一个问题可以归结到对更小问题的计算上。比如0-1背包中计算F(i,j)可以归结到对F(i-1,j-need[i])的计算上。对于两个问题F(i,j)和F(i',j')，如果都能归结到对子问题F(a,b)的计算上，则F(a,b)不需要重复计算两次，因为F(a,b)的计算结果已经被保存下来了。
无后效性：如果计算F(i,j)时用到了已经计算好的F(a,b)的值，我们无需关心F(a,b)的值究竟是对应着哪一种选择方案，它的具体选择方案不会对之后的决策产生影响。我们只需要关心F(a,b)的值本身。

三、引子二：完全背包

对于完全背包，和0-1背包相比的不同之处在于每件物品可以选取很多次，我们可以建立一个与0-1背包类似的状态转移方程：对于第i件物品，我们可以枚举选择它的次数k，其取值范围为[0,j/need[i]]。所以状态转移方程为：
F(i,j) = max{F(i-1, j-need[i]*k)+value[i]*k}
在上述算法中，计算每个F(i,j)的值需要循环k次，这使得该算法的时间复杂度几乎等于O(N*M^2)。经过观察发现，该算法进行了大量的重复计算，我们可以对该算法进行改进，改进之后的状态转移方程为：
F(i,j) = max{F(i-1,j), F(i,j-need[i])+value[i]}
计算每个F(i,j)的值只需要O(1)的时间复杂度。其中，前一项表示不选第i件物品；后一项表示选第i件物品一次，注意到选择完这一次之后，还是继续讨论对第i件物品的选择。这样重复计算就被消除了，时间复杂度被降低到O(N*M)。另外，像0-1背包一样，完全背包也可以将空间从O(N*M)优化为O(M)。

四、“刷油漆”问题之解

我们令F(node,i,j)表示为结点node分配j个刷油漆的指标（即以node为根的子树中有j个结点被刷油漆），然后从该结点的前i个子结点中选择，总共可以达到的最大价值。这样我们要求的最终结果可以表示为F(root,root->childCount,M)。
我们假设我们为子结点node->child[i]分配k个指标，那么这个子结点可以提供的最大价值为F(node->child[i],node->child[i]->childCount,k)。除去该子结点之外，我们只剩下j-k个指标分配给node->child[i]之前的结点了，这些结点能提供的最大价值为F(node,i-1,j-k)。根据上面的分析，我们可以列出状态转移方程：
F(node,i,j)=max{F(node,i-1,j-k)+F(node->child[i],node->child[i]->childCount,k)}
上面的等式中k的取值范围为[0,j-1]，因为根据题意，为以结点node为根的子树刷油漆时，需要最先为node结点本身刷油漆，所以分配的j个指标中有一个是给node自己的，能分配给node的某个子结点的指标最多只有j-1个。
进一步地，我们讨论一些边界情况：
j=0的时候，也就是没有为结点node分配任何指标，最后的价值肯定为0；
j=1的时候，只能为结点node本身刷油漆，所以最后的价值肯定为v[node]；
i=0且j>0的时候，即使为结点node分配的指标再多，因为不选任何一个子结点，所以最后的价值也只能是v[node]。

那么应该如何实现上述状态转移方程呢？一般情况下，动态规划可以用数组来实现，数组的每一个维度对应状态转移方程中的一个参数。但是本题并不适用，因为数组不方便表示树中结点的父子关系。本题需要用的方法叫做树形DP，它将树的遍历和动态规划结合到一起：在树中的每个结点上都定义一个动态规划的表格，对父结点表格的计算依赖于子结点表格的计算结果，这就决定了我们可以通过一趟后序遍历将所有结点的表格填充完毕。

刷油漆

struct Node{
    int label;
    bool visited; //该结点是否已经开始访问；
    int childCount; //子结点个数；
    vector<vector<int>> table; //该结点对应的动态规划表格，大小是(k+1)*(M+1)，其中k为该结点的子结点个数；
    vector<Node*> neighbors;
    vector<Node*> child;
    Node(int l = 0): label(l), visited(false), childCount(0), neighbors(vector<Node*>()), child(vector<Node*>(1, NULL)){}
};

void traverse(Node* node, const int& M, const vector<int>& value){
    node->visited = true;

    //遍历每个子结点：
    for(int i=0; i<node->neighbors.size(); i++){
        Node* curNeighbor = node->neighbors[i];
        if(!curNeighbor->visited){
            node->childCount++;
            node->child.push_back(curNeighbor);
            traverse(curNeighbor, M, value);
        }
    }

    node->table = vector<vector<int>>(node->childCount+1, vector<int>(M+1, 0));
    for(int i=0; i<=node->childCount; i++)
        node->table[i][1] = value[node->label];
    for(int j=1; j<=M; j++)
        node->table[0][j] = value[node->label];
    for(int i=1; i<=node->childCount; i++){
        for(int j=2; j<=M; j++){
            //可以为第i个子结点分配0...j-1个空间，分配0个空间即不选择第i个子结点：
            int maxValue = 0;
            for(int k=0; k<=j-1; k++)
                maxValue = max(maxValue, node->table[i-1][j-k] + node->child[i]->table[node->child[i]->childCount][k]);
            node->table[i][j] = maxValue;
        }
    }
}

int main(){
    int vertexNum, M;
    cin >> vertexNum >> M;
    vector<Node*> graph(vertexNum+1, NULL);
    vector<int> value(vertexNum+1);
    for(int i=1; i<=vertexNum; i++)
        cin >> value[i];
    int vertex1, vertex2;
    for(int i=0; i<vertexNum-1; i++){
        cin >> vertex1 >> vertex2;
        if(!graph[vertex1])
            graph[vertex1] = new Node(vertex1);
        if(!graph[vertex2])
            graph[vertex2] = new Node(vertex2);
        graph[vertex1]->neighbors.push_back(graph[vertex2]);
        graph[vertex2]->neighbors.push_back(graph[vertex1]);
    }
    Node* root = graph[1];
    //在一次后序遍历的过程中为每个结点生成动态规划表格：
    traverse(root, M, value);
    //最后结果对应F(root, root->childCount, M);
    cout << root->table[root->childCount][M];
    //Delete:
    for(int i=1; i<vertexNum; i++)
        if(graph[i])
            delete graph[i];
    return 0;
}

美柑の部屋

涙は見せないと誓った。

Loading…