算法提高之有依赖的背包问题
-
核心思想：分组背包 + 树形dp
- 因为不取父节点，子节点取不了 所以dfs递归从子节点开始，向上返回
- f[i][j]表示以i为根节点总体积不超过j的方案
-
#include <iostream>#include <cstring>#include <algorithm>using namespace std;const int N = 110;int e[N],ne[N],h[N],idx;int v[N],w[N];int f[N][N];int n,m,root;void add(int a,int b) //存图{e[idx] = b,ne[idx] = h[a],h[a] = idx++;}void dfs(int u) //递归{for(int i=h[u];~i;i=ne[i]) //遍历子节点{int son = e[i]; //取子节点dfs(son);for(int j=m-v[u];j>=0;j--) //确保能取到当前父节点 预留v[u]的体积{ for(int k=0;k<=j;k++) //子节点占用的体积{//01背包 j从大到小 求f[u][j]时f[u][j-k]还没更新 即当前子节点没有算进去f[u][j] = max(f[u][j] , f[u][j-k] + f[son][k]);}}}//所有能放当前父节点的都放一下for(int j=m;j>=v[u];j--) f[u][j] = f[u][j-v[u]] + w[u]; //所有放不了父节点的全部清空 放不了父节点-->什么都放不了for(int j=0;j<v[u];j++) f[u][j] = 0;}int main(){cin>>n>>m;memset(h, -1, sizeof h);for(int i=1;i<=n;i++){int p;cin>>v[i]>>w[i]>>p;if(p == -1) root = i;else add(p,i);}dfs(root);cout<<f[root][m]<<endl;return 0;}
