树上分组背包问题

yuanheci 2023年03月28日 681次浏览

  第一次碰到这种树上的背包问题，记录一下，后续会慢慢补充。

题目链接 《P1273 有线电视网》

关键：
  把每个结点看成一个背包，体积就是该结点为根的子树中的用户总数量。并且以该结点为根的子树中的用户选择数量作为不同组别（每一种数量看成是组内的一种物品），进行分组背包求解。

完整的状态定义为三维：

  f[u][i][j]:f[u][i][j]: 表示以 uu 为根的子树，且只选其中的 ii 个用户，所选用户数量不超过 jj 的方案集合的最大价值。

状态转移方程：

  f[u][i][j]=max(f[u][i−1][j−k]+f[son][size(son)][k]−cost[u][son])f[u][i][j] = max(f[u][i - 1][j - k] + f[son][size(son)][k] - cost[u][son])。

  • son表示选择的某个子结点.
  • k表示分给son的体积。

  三维会 MLEMLE，因此可以根据转移方程优化掉第一维，由于树形DPDP采用 dfsdfs 形式，是自底向上的，所以在计算以 uu 为根结点时，以 sonson 为根的情况已经算完了，所以 f[son][k]f[son][k] 这一项不受影响。而前一项需要类比 0101 背包，对体积从大到小枚举。

  因此二维状态表示 f[u][j]f[u][j] 对应的转移方程如下：

  f[u][j]=max(f[u][j−k]+f[son][k]−cost[u][son])f[u][j] = max(f[u][j - k] + f[son][k] - cost[u][son])

答案： 统计一遍，f[1][j]≥0f[1][j] \ge 0 时最大的 jj 就是答案。

注意： ff 的初始化

AC代码：

  1. #include <bits/stdc++.h>
  2. using namespace std;

  4. const int N = 3010;
  5. int h[N], e[N], w[N], ne[N], idx;
  6. int val[N], f[N][N];  //f[i][j]: 以i为根结点，选择用户数量不超过j的方案的最大价值，答案就是f[1][j] > 0中的Max(j) 
  7. int n, m;
  8. int ans;

  10. void add(int a, int b, int c){
  11. 	e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
  12. }

  14. int dfs(int u, int p){
  15. 	if(u > n - m){  //已经到达用户终端 
  16. 		f[u][1] = val[u];
  17. 		return 1;
  18. 	}
  19. 	int s = 0;
  20. 	for(int i = h[u]; ~i; i = ne[i]){
  21. 		int son = e[i];
  22. 		if(son == p) continue;
  23. 		int t = dfs(son, u);
  24. 		s += t;
  25. 		for(int j = m; j >= 0; j--){
  26. 			//分组选取
  27. 			for(int k = 0; k <= t; k++){
  28. 				if(j - k >= 0) f[u][j] = max(f[u][j], f[u][j - k] + f[son][k] - w[i]);
  29. 			} 
  30. 		}
  31. 	}
  32. 	return s;
  33. }

  35. void solve(){
  36. 	scanf("%d%d", &n, &m); 
  37. 	memset(h, -1, sizeof h);
  38. 	memset(f, -0x3f, sizeof f);
  39. 	for(int i = 1; i <= n - m; i++){
  40. 		int k;
  41. 		scanf("%d", &k);
  42. 		for(int j = 0; j < k; j++){
  43. 			int x, c;
  44. 			scanf("%d%d", &x, &c);
  45. 			add(i, x, c);
  46. 		}
  47. 	}
  48. 	for(int i = n - m + 1; i <= n; i++) scanf("%d", &val[i]);
  49. 	for(int i = 1; i <= n; i++) f[i][0] = 0;
  50. 	dfs(1, -1);

  52. 	for(int j = m; j >= 0; j--){
  53. 		if(f[1][j] >= 0){
  54. 			ans = j;
  55. 			break;
  56. 		}
  57. 	}
  58. 	printf("%d\n", ans);
  59. }

  61. int main(){
  62. 	int T = 1;
  63. //	scanf("%d", &T);
  64. 	while(T -- ){
  65. 		solve();
  66. 	}
  67. 	return 0;
  68. }
上一篇： 组合数学——康拓展开