小杨买饮料
spilt
·
·
题解
洛谷 B3873
01 背包问题，如果不知道 01 背包请参考这里。
题目大意
给你 n 个重量为 c_i 价值为 l_i 的物品，每件物品只能选一次，问你要获得 L 的价值最少需要多少重量。
思路简述
首先用 01 背包的模版求出用 i 的重量最多能获得多少价值，重量的最大值为 \begin{aligned}\sum_{i=1}^nc_i \end{aligned}，然后从 0 开始循环一遍，如果用 i 的重量可以获得超过 L 的价值，那么就输出 i，并且结束程序。