T3.评估最大工作量(300分) - 华为机试真题题解

考试平台： 时习知

分值： 300分（第三题）

考试时间： 两小时（共3题）

题目描述

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

输入

输入共两行

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

次行有n个整数，以空格隔开，分别是，代表每个需求所需作量，单位是人天

数据范围：

输出

一个整数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人天、5人天、8人天、10人天，小梁选择全部需求，所需工作量总和是1+2+7+5+8+10=33

示例3

输入：
6 100
101 102 103 104 105 106

输出：
0

解释： 
所有需求都不能完成

题解

这道题可以用递归回溯法解决。在递归过程中，不断尝试选择或者不选择当前需求，然后计算工作量是否超过了预算 T，如果没有超过则继续递归下一个需求，直到所有需求都尝试完毕。

解题思路：

1. 使用递归函数 dfs，传入当前需求的索引 idx、当前已经完成的工作量 sumwork，以及需求数组 requirements。
2. 在每一次递归中，首先检查当前工作量是否超过了预算 T，如果超过则直接返回。
3. 在每一次递归中，都更新最大工作量