5922: 【DP】华为2024秋招-评估最大工作量

金币值:1 时间限制:4.000 s 内存限制:128 M
正确:11 提交:25 正确率:44.00% 命题人:
点赞量:0 收藏量:0 题目类型:程序 知识点: 背包问题 DP 华为

题目描述

其团队以来了一个大项目,该项目己知有n个需求,每个需求工作量分别需要有t1、t2…tn人天,由于该项目需求过多,负责人小梁决定先给出1人天预算完成部分需求。对于单个需求,每个任务要么不做,要么全部完成,必须耗时ti人天完成,现在小梁想知道t人天的预算最多能做多少人天的需求。

输入格式

输入共两行
首行是2个整数,以空格隔开,分别是nTn代表需求总教,T代表工作量评估不超过T人天
次行有n个整数,以空格隔开,分别是t1、t2…tn,代表每个需求所需工作量,单位是人天
数据范围:1<=n<=40; 1<=ti<=10^5;1<=T<=10^5

输出格式

一个整数ans,代表T人天的预算最多能做ans人天的需求

输入样例    复制

5 17
2 3 5 11 7

输出样例    复制

17