E. 【入门】多重背包

传统题

1000ms

256MiB

题目描述

有 $N$ 种物品和一个容量是 $V$ 的背包。

第 $i$ 种物品最多有 $s_i$ 件，每件体积是 $v_i$ ，价值是 $w_i$ 。

求解将哪些物品装入背包，可使物品体积总和不超过背包容量，且价值总和最大。输出最大价值。

第一行两个整数， $N，V$ ，用空格隔开，分别表示物品种数和背包容积。

接下来有 $N$ 行，每行三个整数 $v_i, w_i, s_i$ ，用空格隔开，分别表示第 $i$ 种物品的体积、价值和数量。

输出一个整数，表示最大价值。

【样例解释 1】

请思考后再点击查看提示

本题考查多重背包的 二进制优化 方法
假设某个物品的数量是 10，体积是 $v$ ，价值是 $w$
将 10 表示成 $10=2^0+2^1+2^2+3=1+2+4+3$
我们可以将这个物品拆分成 4 个物品
- 物品 1：体积 1 * v，价值 1 * w
- 物品 2：体积 2 * v，价值 2 * w
- 物品 3：体积 4 * v，价值 4 * w
- 物品 4：体积 3 * v，价值 3 * w
不管原来的物品取了多少个，都可以有拆分成的新的 4 个物品组合而成
因此，可以将所有的物品都按照上述方法拆分，然后做按 01背包求解