AcWing 10. 有依赖的背包问题
原题链接
困难
作者:
_cc
,
2022-01-21 15:51:17
,
所有人可见
,
阅读 319
C++ 代码
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N=105;
int f[N][N];
int n,m;
int v[N],w[N],p;
int e[N],ne[N],h[N],idx;
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!=-1;i=ne[i]){ //一个节点当做一个物品,枚举节点
int t=e[i];
dfs(t);
for(int j=m-v[u];j>=0;j--){ //不选节点u时体积为j的最大价值(这里是按体积分组)
for(int k=0;k<=j;k++){ //枚举每一种决策
f[u][j]=max(f[u][j],f[u][j-k]+f[t][k]);
}
}
}
for(int j=m;j>=v[u];j--) f[u][j]=f[u][j-v[u]]+w[u]; //加上节点u的最大价值
for(int j=1;j<v[u];j++) f[u][j]=0; //体积装不下节点u,价值为0
}
int main(){
memset(h,-1,sizeof h);
scanf("%d%d",&n,&m);
int root;
for(int i=1;i<=n;i++){
scanf("%d%d%d",&v[i],&w[i],&p);
if(p==-1) root=i;
add(p,i);
}
dfs(root);
cout<<f[root][m];
return 0;
}