题面解释:

小塔的团队面临一个大项目，包含$n$个需求，每个需求需要不同的人天工作量。团队的工作量预算为$T$人天，目标是选择一些需求，使得在不超过$T$人天的前提下，所选需求的工作量总和最大。每个需求要么全部完成，要么不做。输入包含两行，第一行是两个整数$n$和$T$，第二行是$n$个整数，表示每个需求的工作量。输出一个整数，表示在预算内可以完成的最大工作量。

题解

该题可以使用状态压缩动态规划（DP）或深度优先搜索（DFS）结合二分查找来解决。由于背包容量可达到 10^9，而物品数量 n 为 40，使用普通的 01 背包算法显然不可行，因为 2^40 的复杂度会爆炸。因此，我们可以将物品分成两个组，每组最多有 20 个物品，这样总的复杂度将减少到 2^20，大约在 100 万级别，仍然可以接受。

具体思路如下：

题目内容

某团队来了一个大项目，该项目已知有$n$个需求，每个需求工作量分别需要$t_1、t_2、t_3.......t_n$人天，由于该项目需求过多，负责人小明决定先给出$T$人天预算完成部分需求。对于单个需求，每个任务要么不做，要么全部完成，必须耗时$ti$人天完成，现在小明想知道$T$人天的预算最多能做多少人天的需求。

输入描述

输入共两行

首行是$2$个整数，以空格隔开，分别是$n$和$T$，$n$代表需求总数，$T$代表工作量评估不超过$T$人天

次行有$n$个整数，以空格隔开，分别是$t_1、t_2、t_3....t_n$，代表每个需求所需工作量，单位是人天

数据范围:$1≤n≤40;1≤ti≤10^9;1≤T≤10^9$

输出描述

一个整数$Ans$，代表$T$人天的预算最多能做$Ans$人天的需求

样例1

输入

5 17
2 3 5 11 7

输出

17

说明

该项目有$5$个需求，工作量评估不超过$17$人天，每个需求工作量分别需要$2$人天、$3$人天、$5$人天、$11$人天、$7$人天;

小明选择需求$1$、需求$2$、需求$3$、需求$5$，所需工作量总和是$2+3+5+7=17$

样例2

输入

6 100
1 2 7 5 8 10

输出

33

说明

该项目有$6$个需求，工作量评估不超过$100$人天，每个需求工作量分别需要$1$人天、$2$人天、$7$人天、$6$人天、$8$人天、$10$人天;

小明选择全部需求，所需工作量总和是$1+2+7+5+8+10=33$

样例3

输入

6 100
101 102 103 104 105 106

输出

0

说明

该项目有$6$个需求，工作量评估不超过$100$人天，每个需求工作量分别需要$101$人天、$102$人天、$103$人天、$104$人天、$105$人天、$106$人天;

小明无论选择哪个需求都超过了$100$人天，所需工作量总和最大是$0$人天