08764. 民乐团的运输箱 · 林老师的题库

题目描述

民乐团期末要去音乐厅汇报演出，租用的运输车上只放得下一个乐器运输箱。运输箱内部容积为 $V$ 立方分米，团里共有 $n$ 件乐器想运过去，第 $i$ 件乐器（连同琴盒）装箱后占 $c_{i}$ 立方分米。每件乐器最多装一件，也可以一件都不装。

团长希望运输箱尽可能装满。请计算箱内剩余空间最小是多少立方分米。

第一行两个整数 $n$ 和 $V$ ，表示乐器件数与运输箱容积（立方分米）。

接下来 $n$ 行，每行一个整数 $c_{i}$ ，表示第 $i$ 件乐器装箱后所占的体积。

一行一个整数，表示箱内剩余空间的最小值（立方分米）。

输入

输出

样例解释：装第 $1$ 、 $2$ 、 $3$ 件乐器，占用 $9 + 12 + 6 = 27$ 立方分米，剩余 $28 - 27 = 1$ 立方分米；没有任何方案能恰好装满箱子。

样例解释：只有一件乐器，占 $33$ 立方分米，装进后剩余 $50 - 33 = 17$ 立方分米。

对于 $100%$ 的数据： $1 \leq n \leq 100$ ， $0 \leq V \leq 1 0^{4}$ ， $1 \leq c_{i} \leq 3000$ 。

本题共 $10$ 个测试点，每个测试点 $10$ 分。