Skip to content

1115: Interesting Knapsack

题目

题目描述

存在N个物品,第i个物品有重量wi与价值vi,并且第i个物品可能依赖于第j件物品。

依赖的意思是指,你如果想购买第i个物品,必须购买过第j件物品。保证依赖关系不会构成环,并且每件物品至多存在一个依赖的物品。

求给定背包可容纳重量后,你可以装最多多少价值的物品。

输入格式

第1行,两个整数N,W,代表物品个数以及背包容量。

第2~N+1行,每行三个整数Fi, Wi, Vi,代表第i个物品的依赖物品,重量,价值。

注意,物品从1开始编号,当Fi=0的时候,意味着该物品不需要依赖任何其他物品。

输出格式

一个整数,代表最大价值和。

样例输入

Sample Input 1

5 5
0 1 2
0 2 3
0 3 5
0 4 4
0 5 7

Sample Input 2

5 5
0 1 1
1 1 1
2 1 1
3 1 1
4 1 1
5 1 1000

样例输出

Sample Output 1

8

Sample Output 2

5

数据范围

  • 对于30%的数据,满足 N<=18(该部分其中一半数据,全部的物品Fi=0);
  • 对于另外30%的数据,满足 N<=1000(全部的物品Fi=0);
  • 对于另外20%的数据,满足 N<=100;
  • 对于100%的数据,满足 N<=1000.
  • W与N数据范围一致。
  • Wi,Vi全部为非负整数,答案在int以内.

Oops! 本题目还没有解答!

助教老师们编题的速度,已经超过了解题的速度!

OJ翻了一新,但本解答集还大多用的是2017-2019级,甚至更早的同学们贡献的答案。

如果你已经AC了,可以的话,请您参考添加页面,与大家一起分享你的题解!