大家好，今天我遇到了一个有意思的问题，叫做“查找充电设备组合”。问题大意是我们有很多充电设备，每个设备都有不同的输出功率，我们需要找到最接近但不超过充电站最大输出功率p_max的一组设备组合。听起来像是一个经典的子集和问题，但我得想个高效的办法来解决这个问题。先从简单的情况入手，比如说有4个设备，功率分别是50、20、20、60，p_max是90，这时候最优解就是50+20+20=90，刚好等于p_max。那么如果设备数量很大呢？我们不能一个个枚举所有组合，那样太慢了。于是我想到可以使用动态规划的方法。动态规划可以用来解决这类问题，通过记录哪些总和是可以达到的。具体来说，我们可以用一个布尔数组dp，dp[i]表示是否可以达到总和i。初始化dp[0]=true，然后对于每一个设备的功率，我们遍历dp数组，把当前设备的功率加到以前可以达到的所有总和上。最后，从最大的可能总和往0找，找到第一个为true的，就是我们想要的答案。比如说，处理完50、20、20、60之后，我们就能在dp数组中找到90的位置，就是我们要求的结果。那如果p_max小于所有设备的总和呢，比如p_max是80，这时候最优答案就是70，这是小于80的最接近的数。看来动态规划的方法不仅高效，还能处理各种情况。下次遇到类似的问题，我也可以用这个方法了。总之，这个问题让我对子集和问题和动态规划有了更深的理解，感觉又学到了新知识！

查找充电设备组合

时间限制：5s空间限制：256MB限定语言：不限

题目描述：

某个充电站，可提供n个充电设备，每个充电设备均有对应的输出功率。任意个充电 设备组合的输出功率总和，均构成功率集合P的1个元素。功率集合P的最优元素，表 示最接近充电站最大输出功率p max的元素。

输入描述：

输入为3行：
第1行为充电设备个数n。
第2行为每个充电设备的输出功率。
第3行为充电站最大输出功率p_max。

输出描述：

功率集合P的最优元素

补充说明：

1.充电设备个数n>0
2.最优元素必须小于或等于充电站最大输出功率p_max。

示例1

输入：

4
50 20 20 60
90

输出：

90