首页 > 试题广场 >

【模板】二维费用背包

[编程题]【模板】二维费用背包
  • 热度指数:490 时间限制:C/C++ 5秒,其他语言10秒 空间限制:C/C++ 512M,其他语言1024M
  • 算法知识视频讲解
\hspace{15pt}小红非常喜欢在社交平台分享生活点滴。她的生活中共有 n 个事件,第 i 个事件若要发布,需要耗费 t_i 分钟时间与 h_i 点精力,并能让她获得 a_i 点快乐值。

\hspace{15pt}在本次挑战中,小红希望在总耗时不超过 T,总消耗精力不超过 H 的前提下,选择若干事件进行分享,使得收获的快乐值总和最大。请你帮她计算她最多能获得多少快乐值。

输入描述:
\hspace{15pt}第一行输入一个整数 n\ (1\leqq n\leqq50)——事件数量。

\hspace{15pt}第二行输入两个整数 T,H\ (1\leqq T,H\leqq500)——可用时间与可用精力上限。

\hspace{15pt}接下来 n 行,第 i 行输入三个整数 t_i,h_i,a_i\ \bigl(1\leqq t_i,h_i\leqq30,\ 1\leqq a_i\leqq10^9\bigr),描述第 i 个事件的参数。


输出描述:
\hspace{15pt}输出一个整数,代表在限制条件内能获得的最大快乐值。
示例1

输入

3
5 4
1 2 2
2 1 3
4 1 5

输出

7

说明

选择事件 1 与事件 3:耗时 1+4=5\leqq T,耗费精力 2+1=3\leqq H,快乐值 2+5=7
示例2

输入

2
2 2
1 3 3
3 1 4

输出

0

说明

任何单个事件都超过精力或时间限制,小红只能选择不分享,快乐值为 0

这道题你会答吗?花几分钟告诉大家答案吧!