AcWing 10. 有依赖的背包问题 Java
原题链接
困难
作者:
小赵想滑板
,
2024-01-23 17:08:59
,
所有人可见
,
阅读 33
Java 代码
import java.util.*;
public class Main{
static Scanner sc=new Scanner(System.in);
static int N=110;
static int n,m,idx;
static int v[]=new int [N];
static int w[]=new int[N];
static int h[]=new int[N];
static int e[]=new int[N];
static int ne[]=new int[N];
static int f[][]=new int[N][N];
static void add (int a,int b){
e[idx]=b;ne[idx]=h[a];h[a]=idx++;
}
static void dfs(int u){
for(int i=h[u];i>=0;i=ne[i]){//1循环物品组
int son=e[i];
dfs(e[i]);
//分组背包
for(int j=m-v[u];j>=0;j--)//2循环体积
for(int k=0;k<=j;k++)//3循环决策
f[u][j]=Math.max(f[u][j],f[u][j-k]+f[son][k]);
}
//将物品u加进去
for(int i =m;i>=v[u];i--) f[u][i]=f[u][i-v[u]]+w[u];
for(int i=0;i<v[u];i++) f[u][i]=0;
}
public static void main(String[]args){
n=sc.nextInt();
m=sc.nextInt();
Arrays.fill(h,-1);
int root=0;
for(int i=1;i<=n;i++){
int p;
v[i]=sc.nextInt();
w[i]=sc.nextInt();
p=sc.nextInt();
if(p==-1) root=i;
else add(p,i);
}
dfs(root);
System.out.println(f[root][m]);
}
}