自动搬运

查看原文

来自洛谷，原作者为

	ruanshaochuan______ 3884618690

搬运于2025-08-24 21:15:38，当前版本为作者最后更新于2023-11-11 10:48:27，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

洛谷 B3873

01 背包问题，如果不知道 01 背包请参考这里。

题目大意

给你 $n$ 个重量为 $c_i$ 价值为 $l_i$ 的物品，每件物品只能选一次，问你要获得 $L$ 的价值最少需要多少重量。

思路简述

首先用 01 背包的模版求出用 $i$ 的重量最多能获得多少价值，重量的最大值为 $\begin{aligned}\sum_{i=1}^nc_i \end{aligned}$，然后从 $0$ 开始循环一遍，如果用 $i$ 的重量可以获得超过 $L$ 的价值，那么就输出 $i$，并且结束程序。