解题思路

每箱最多装一次，总公斤数不能超过承重，目标是售价之和最大。这是 0-1 背包。

令 $dp[room]$ 表示承重只用到 $room$ 公斤时，目前能凑出的最高售价。一开始一箱都没装，全部是 $0$ 。
逐箱考虑。处理第 $i$ 箱时，承重从 $C$ 往公斤数 $g$ 倒着更新： $dp[room] = \max(dp[room], dp[room - g] + p)$ 。
倒着扫是为了这一箱只被使用一次。从低往高扫会把同一箱的售价反复加上。
公斤数大于当前承重的箱子自然进不了循环，相当于不装。
答案是 $dp[C]$ 。所有箱子都装不上时，它仍是 $0$ 。

题目内容

码头有若干箱货，每箱有自己的公斤数和售价。货舱还剩一段承重。每箱最多装一次，也可以不装。在总公斤数不超过剩余承重的前提下，让装上船的售价之和尽量大。

第一行两个整数 $m$ 和 $C$ 。 $m$ 是箱数， $C$ 是货舱还能承受的公斤数。

接下来 $m$ 行。每行两个整数 $g$ 和 $p$ ，依次是这一箱的公斤数和售价。

$1 \le m \le 100$ ， $1 \le g \le 1000$ ， $1 \le p \le 1000$ ， $1 \le C \le 10000$ 。

输出一行一个整数，表示能装上船的最大售价之和。一箱都不装时，这个和是 $0$ 。

说明

后两箱一共 $4 + 4 = 8$ 公斤，售价 $7 + 7 = 14$ 。只装第一箱得到 $10$ ，剩下 $3$ 公斤放不进另外两箱。第一箱再加任意一箱都会超过 $8$ 公斤。

2 3
4 8
5 9

说明

两箱分别是 $4$ 公斤和 $5$ 公斤，都比货舱剩下的 $3$ 公斤更重，只能空着走。

选择提交后点击「开始AI分析」