有依赖的背包问题（Acwing 10）


 1 # include<iostream>
 2 # include<cstring>

 3 # include<algorithm>

 4 using namespace std;

 5 const int N = 110;

 6

 7 int e[N], ne[N], idx;

 8 int h[N];

 9 int v[N], val[N];

10 int n, m;

11 int f[N][N];

12

13 void add(int a, int b) {

14     e[idx] = b;

15     ne[idx] = h[a];

16     h[a] = idx++;

17 }

18 void dfs(int u) {

19     for (int i = h[u]; ~i; i = ne[i]) /*循环子节点*/

20     {

21         int son = e[i];

22         dfs(e[i]);/*递归子节点*/

23

24         for (int  j = m - v[u]; j >= 0; --j)/*循环体积*/

25             for (int k = 0; k <= j; ++k)/*循环决策*/

26                 f[u][j] = max(f[u][j], f[u][j - k] + f[son][k]);

27     }

28     for (int i = m; i >= v[u]; i--) f[u][i] = f[u][i - v[u]] + val[u];

29     for (int i = 0; i < v[u]; ++i) f[u][i] = 0;

30 }

31

32 int main() {

33     cin >> n >> m;

34     int root;/*根节点*/

35     memset(h,-1,sizeof h);/*初始化头结点*/

36     for (int i = 1; i <= n; ++i) {

37         int c;

38         cin >> v[i] >> val[i] >> c;

39         if (c == -1) root = i;

40         else add(c, i);

41     }

42

43     dfs(root);

44

45     cout << f[root][m] << endl;

46     return 0;

47 }

f[u][j]表示在根节点为u，体积为j的情况下的最大价值

树形结构的dp问题，重点在于理解在树形结构的决策选择

因为题目限制只要选择子节点，那么头结点必须选择，所以在循环体积的时候，因为是对于子节点进行循环体积

所以要求要在体积上为父节点的体积预留位置，所以才有：

for (int  j = m - v[u](这一步就是在为父节点预留体积); j >= 0; --j)

而在后续的的过程中，因为在递归字节的时候为父节点预留了体积，所以在结束对子节点的递归后
需要把之前预留的位置将父节点的信息加进去，也就是：

for (int i = m; i >= v[u]; i--) f[u][i] = f[u][i - v[u]] + val[u];
　　对于之前预留的体积将父节点的信息加入进去，

for (int i = 0; i < v[u]; ++i) f[u][i] = 0;
因为只要选择子节点就需要选择父节点，所以对于小于父节点的部分在决策中是绝对选择不到的
这就需要将其价值清0

巴特西

有依赖的背包问题（Acwing 10）

最新文章

热门文章