P2925 [USACO08DEC] Hay For Sale S

【题意】

有 $n$ 个物品，每个物品的体积为 $v_i$ 。

选若干个物品装入一个体积为 $V$ 的背包，使得所选物品的体积和 $s$ 尽量接近 $V \ (s \le V)$ ，求 $s$ 的最大值。

【输入格式】

第一行两个整数 $V \ n \ (1 \le V \le 5 \times 10^4，1 \le n \le 5 \times 10^3)$ 。

下来 $n$ 个整数 $v_i(0 \le v_i \le 20000)$ 。

【输出格式】

一个整数，表示 $s$ 的最大值。

【样例输入】

7 3 
2 6 5

【样例输出】

7