AcWing 10. 有依赖的背包问题
原题链接
困难
作者:
Tyouchie
,
2019-08-21 12:16:48
,
所有人可见
,
阅读 1358
C++ 代码
#include<bits/stdc++.h>
using namespace std;
const int N=1001;
int n,m,tot,lin[N],v[N],w[N],root,p;
int f[1010][1010];//表示将i为根的子树内选取了容量为j的物品所获得的最大价值;
struct gg {
int y,next;
}a[N];
inline void add(int x,int y) {
a[++tot].y=y; a[tot].next=lin[x]; lin[x]=tot;
}
inline void dfs(int x) {
for(int i=lin[x];i;i=a[i].next) {
int y=a[i].y;
dfs(y);
for(int j=m-v[x];j>=v[y];j--) {
for(int k=v[y];k<=j;k++) {
f[x][j]=max(f[x][j],f[x][j-k]+f[y][k]);
}
}
}
for(int i=m;i>=v[x];i--) {
f[x][i]=f[x][i-v[x]]+w[x];
}
for(int i=0;i<v[x];i++) {
f[x][i]=0;
}
}
int main() {
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++) {
scanf("%d%d%d",&v[i],&w[i],&p);//体积价值;
if(p==-1) root=i;
else add(p,i);
}
dfs(root);
cout<<f[root][m];
return 0;
}