353. 多重背包问题 II
时间限制：1000 MS 内存限制：64 MB
题目描述
# 多重背包问题 II ## 题目描述 有 $N$ 种物品和一个容量为 $V$ 的背包。 第 $i$ 种物品最多有 $s_i$ 件，每件物品的体积为 $v_i$，价值为 $w_i$。 你可以从每种物品中选取若干件，选取数量必须为整数，且不能超过该种物品的数量限制。请在所选物品总体积不超过 $V$ 的前提下，求所能获得的最大总价值。 ## 输入格式 从文件 `multik.in` 中读入数据。 第一行包含两个整数 $N$ 和 $V$，用空格隔开，分别表示物品种数和背包容量。 接下来 $N$ 行，第 $i$ 行包含三个整数 $v_i$、$w_i$ 和 $s_i$，用空格隔开，分别表示第 $i$ 种物品每件的体积、每件的价值和最多可选取的数量。 ## 输出格式 将结果输出到文件 `multik.out` 中。 输出一个整数，表示所选物品总体积不超过 $V$ 时的最大总价值。 ## 数据范围 所有输入数据均为整数，且满足： - $1 \le N \le 1000$； - $1 \le V \le 2000$； - 对于所有 $1 \le i \le N$，有 $1 \le v_i,w_i,s_i \le 2000$。 ## 样例输入 ``` 4 5 1 2 3 2 4 1 3 4 3 4 5 2 ``` ## 样例输出 ``` 10 ``` ## 提示 本题考查多重背包的二进制优化方法。 ## 时间与空间限制 - 时间限制：$1000$ 毫秒。 - 空间限制：$64$ MB。