j01707. 最近子集和 · 林老师的题库

题目描述

给定 $n$ 个正整数 $a_{1}, a_{2}, \dots, a_{n}$ ，以及一个上限 $l imi t$ 。

请从这些数中选出一个子集（每个数至多选一次），要求子集的和不超过 $l imi t$ ，并且尽量接近 $l imi t$ （即不超过 $l imi t$ 的前提下尽量大）。

输出这个最接近的子集和。特别地，什么都不选时子集和为 $0$ 。

第一行两个整数 $n$ 和 $l imi t$ 。

第二行 $n$ 个正整数，依次表示每个数。

一行一个整数，表示不超过 $l imi t$ 的最大子集和。

输入

3 10
2 3 5

输出

三个数全选： $2 + 3 + 5 = 10$ ，恰好等于上限 $10$ ，是最接近的方案。

其他组合（ $2 + 3 = 5$ 、 $2 + 5 = 7$ 、 $3 + 5 = 8$ 等）都不超过但离 $10$ 更远。