题目内容

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

输入描述

输入共两行

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

题面解释:

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

题解

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

具体思路如下：