0-1背包，完全背包，树形DP入门

發表於   |   分類於

前面

关于算法这一块，怎么说呢，目前为止我还是比较盲目的在OJ上面A水题，但即便如此AC率也很低——这到底还是不行的，不过终究是给自己探了个底子——在仅有基础概念的RAW状态下能走多远。

就目前来看，很多时候问题出在自己见得少，给不出思路。对于抽象思维要求不高的题目，知道怎么去做之后多数情况还下是能够拿到TLE（并非纯暴搜导致）或者AC的——当然TLE也不是算过，终究还是代码技巧不足；而对于需要有较高抽象能力的题目，或是比较Tricky的题目，则力有不逮——一个是因为见得少而不知道怎么下手，再就是抽象思维能力不过关。

因此，就算法这块，现在开始进行专项练习吧。咱对自己的要求不高，也不指望能有ACM的程度，但至少买的那三本书：《算法竞赛入门经典》、《算法竞赛入门经典训练指南》以及《挑战程序设计竞赛》不能白瞎了。

由于不知道自己对《刷油漆》那道题的题解理解正确与否，文中对那道题目的讲解我是没有信心的，虽然最终代码是AC了……还是要多做多体会。

正文

今次就看三个问题吧，从老生常谈的背包问题开始，到树形DP的简单介绍。

这里先推荐知乎上面关于DP的回答看一看，两个高票答案已经将DP的核心问题讲得很明白了：就是“如何定义状态”以“如何控制状态的转移”——状态转移方程集中体现此两者，至于如何求解（递推或者是记忆化搜索）都只是求解方程的手段而已。

在谨记上面的条款之后，下面开始看3个题目，以协助理解。

0-1背包问题

From：HiHoCoder，HiHo一下第6周。

老题，网上有很多讲解的，包括状态方程怎么来的一应俱全，这里不去赘述，直接给AC的代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#include <iostream>
#include <vector>
using namespace std;
typedef vector<int> vi;

#define INT_MAX 2147483647
#define INT_MIN (-INT_MAX - 1)

int main(int argc, char** argv)
{
	int N = 0, M = 0;
	cin >> N >> M;

	if (N <= 0 || M <= 0) { cout << 0 << endl; return 0; }

	vector<vi> dp(N + 1, vi(M + 1, 0));
	vi need(N + 1, 0);
	vi value(N + 1, 0);

	for (int i = 1; i <= N; ++i)
	{
		cin >> need[i] >> value[i];
	}

	int result = INT_MIN;

	for (int i = 1; i <= N; ++i)
	{
		for (int j = 1; j <= M; ++j)
		{
			if (j < need[i])
			{
				dp[i][j] = dp[i - 1][j];
			}
			else
			{
				int a = dp[i - 1][j];
				int b = dp[i - 1][j - need[i]] + value[i];
				dp[i][j] = (a>b) ? a : b;
			}
			if (dp[i][j] > result)
			{
				result = dp[i][j];
			}
		}
	}
	cout << result << endl;
	return 0;
}

需要注意一下：关于剩余空间M的For循环是从1开始加一递增的；而在采用记忆化搜索的递归解法中，剩余空间M并非是逐1递减的。这里需要逐步领会如何将尾递归转换为迭代的形式（PS：并非是指用显示Stack来辅助的方法）。

完全背包问题

From： HiHoCoder，HiHo一下第7周。

题解HiHo上面已经有了，这里不赘述。下面的AC代码中并没有进行第二步的优化阶段：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

using namespace std;

int VALUE[501];
int NEED[501];
int N, W;

#define INT_MAX 2147483647
#define INT_MIN (-INT_MAX - 1)

int main(int argc, char** argv)
{
	cin >> N >> W;

	for (int i = 0; i < N; ++i)
	{
		cin >> NEED[i + 1] >> VALUE[i + 1];
	}

	int** DP = (int**)new int*[N + 1];
	for (int m = 0; m <= N; ++m)
	{
		DP[m] = new int[W + 1];
		for (int n = 0; n <= W; ++n)
		{
			DP[m][n] = 0;
		}
	}

	for (int i = 1; i <= N; i++)
	{
		for (int j = 1; j <= W; j++)
		{
			int K = j / NEED[i];
			for (int k = 0; k <= K; k++)
			{
				int r = DP[i - 1][j - k*NEED[i]] + k * VALUE[i];
				if (DP[i][j] < r) DP[i][j] = r;
			}
		}
	}

	cout << DP[N][W];

	return 0;
}

刷油漆（树形DP）

From：HiHoCoder，HiHo一下第12周

虽然HiHo有给出题解，但是还是这里还是先借用《训练指南》P70的例题30的讲解开始吧——至少，对于我这种比较笨的人，HiHo的那个题解后半部分一开始是看不太懂的。

当然例题30并非是《刷油漆》原题，但也是树形DP的应用。

下面是整理的引用，需要注意的是后面两句：

无向无环图，或者称为森林，有多棵树组成，动态规划是解决树上的优化问题的常用工具。

为了能够使用动态规划，这要求：森林中的每个节点都互不相干，以便可以单独优化。

我们只考虑一棵树的情况：首先对这棵树进行DFS，将无根树转化为有根树，然后试着设置，并计算它的状态。

我们来看看单独的一棵树的情况，状态的定义HiHo题解中已经说明了，这里主要说明状态转移是如何发生的，也就是HiHo题解后半部分究竟是怎么回事。

先看给出的由case构造出来的树：

case

就从以节点4为根的子树开始吧。

显然我们要在这棵子树中选择三个节点，而如果想要对这棵子树进行评估，那么很显然，节点4也必须被选择（于是我们的DFS也就进行了2层了）。

剩下的两个节点只有从节点4的子树中选取了。

类比背包问题，这就相当于背包只剩下两个空间，而每个节点占用一个空间，选取的物品价值就相当于节点的最大估值，但这个值是存在于DP数组中的，并非是给定的值。

那么，对于节点4的每一个子树，都有可能分配0~2个空间。

这里应当注意：由于采用了DFS，我们已经把节点4的所有子树对应的状态都计算好了，因此，可以认为我们是在背包空间为2的情况下选取下面几个值来达到要求的最大值：

1
2
3
DP[8][0], DP[8][1], DP[8][2]
DP[6][0], DP[6][1], DP[6][2]
DP[7][0], DP[7][1], DP[7][2]

类比完全背包问题：完全背包问题要求对于每种物品选取K个，来得到最大值。这里可以认为是：对于子节点8，选取0~2个；对于子节点6，选取0~2个；对于子节点7，选取0~2个。

这里需要注意的是，上面关于如何选择的情况均是在自顶向下的情况下说明的——而实际代码中，采用的是自底向上的填充方式。

在完全背包中，状态转移方程以及对应代码为：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
DP[i][j] = max{ DP[i][j], DP[i-1][ j-k*w[i] ] + k*v[i] | k = [0...j/w[i]] }

for (int i = 1; i <= N; ++i )
{
  for (int j = 1; j <= M; ++j)
  {
    int K = j/w[i];
    for (int k = 0; k <= K; ++k)
    {
      int r = DP[i-1][j-k*w[i]]+k*v[i];
      if (r > DP[i][j]) DP[i][j] = r;
    }
  }
}

那么，类比可以写出对于单个节点的DP值计算式：

1
DP[i][j] = max{ DP[i][j], DP[i][j-k] + DP[l][k] | l = [i的子节点] }

举个栗子：

1
2
3
4
5
6
7
8
DP[4][3] = DP[4][2] + DP[6][1]
         = max{
                  (DP[4][1] + DP[8][1]),
                  “DP[4][1] + DP[6][1],”
                  (DP[4][1] + DP[7][1])
              } + DP[6][1]  

// 显然max{...}中的DP[6][1]是不应该重复计算的

注意，完全背包的填充方式是在已经有的结果上再装上k个第i种物品（也就是剩余的空间还足够在第i中物品上做出多个选择）；而在当前问题中我们则是在选择了当前子树中的k个节点之后，根节点上还可以再选择多少个其他子树中的节点。

那么尝试写出代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
DFS(int i, int M)
{
  //vis[ci] = true;
  for (each child ci of node i)
  {
      // 不对已经计算过的节点重复计算。
      if (vis[ci]) continue;
      // 先DFS计算子树
      DFS(ci,M-1);
      // 然后根据子树，计算当前节点
      for ( m = [M ... 2]) // 对于 “剩余空间” m
      {
        for ( k = [1 ... m] ) // 接下来要取 k 个节点
        {
          int r = DP[i][m-k] + DP[ci][k];
          if (r > DP[i][m]) DP[i][m] = r;
        }
      }
  }
}

注意到M的值是从大到小计算的，这一点可以从前面列举的那个小例子中看出来：M值大的DP值是依赖于M值小的DP值的。而M的值最小只到2，原因在于，对于M=0时肯定为0，M=1时，就是节点本身。

下面是我的AC代码：

另：如果在HiHo一下的比赛排名中查找AC代码的话，会发现有关于edge、vis数组这样的东西，这是因为那些代码是基于无向图的，需要使用vis数组来标记节点以防止出现环的问题。大部分ACM相关的博客上也是此类型的代码，此类代码更具普适性。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#include<iostream>
#include<fstream>
#include<vector>
using namespace std;

int N, M;
int V[101];
int vis[101];

#define INT_MAX 2147483647
#define INT_MIN (-INT_MAX - 1)

vector<int> Tree[101];

int DP[101][101];

void solve(int n, int m)
{
	vector<int>& children = Tree[n];
	for (auto ci = 0; ci < children.size(); ++ci)
	{
		solve(children[ci], m - 1);

		for (int j = m; j >= 2; --j)
		{
			for (int k = 1; k < j; ++k)
			{
				int r = DP[n][j - k] + DP[children[ci]][k];
				if (r > DP[n][j]) DP[n][j] = r;
			}
		}
	}
}

int main(int argc, char** argv)
{
	// 注意下面的不要删除，重定向io流
	// std::ifstream in("in.txt");
	// std::streambuf* cinbuf = std::cin.rdbuf(); //save old buf
	// std::cin.rdbuf(in.rdbuf()); //redirect std::cin to in.txt!

	//
	cin >> N >> M;
	for (int i = 1; i <= N; ++i) cin >> V[i];
	int a, b;
	for (int i = 1; i < N; ++i)
	{
		cin >> a >> b;
		Tree[a].push_back(b);
	}
	for (int i = 1; i <= N; ++i)
	{
		DP[i][1] = V[i];
	}

	solve(1, M);

	cout << DP[1][M] << endl;

	return 0;
}