Responsive image

问题 2260 --购物

2260: 购物

时间限制: 1 Sec  内存限制: 128 MB
提交: 0  解决: 1
[提交][状态][讨论版][命题人:]

题目描述

双十一就要到来了，商店进行促销降价，但商店老板为了卖掉更多的商品决定在进行捆绑销售，即在购买一个商品时也要购买它所捆绑的商品如果捆绑的商品上也有捆绑商品则也要购买。
现在商店有 n 个商品每个商品价格是 v 价值是 w 捆绑的商品是 s 
你现在有 m 元
求出你能购买到的商品最大价值是多少。
每个商品只能购买一次。

输入描述

第一行有两个整数 N，V用空格隔开，分别表示商品个数和你的金钱的数额。

接下来有 N 行数据，每行数据表示一个商品。
第 i行有三个整数 v ,w , s，用空格隔开，表示第 i 个商品的金额、价值和捆绑商品编号。

如果 s=−1，表示没有捆绑商品。 数据保证无冲突且只有一个无捆绑商品。

输出描述

输出一个整数，表示最大价值。

样例输入

5 7
2 3 -1
2 2 1
3 5 1
4 7 2
3 6 2

样例输出

11

提示

动态规划，dp， 树状dp，背包问题，有依赖的背包




来源

李杨帆 

[提交][状态]
ACM算法攻关部