352. 多重背包问题 I
时间限制：1000 MS 内存限制：64 MB
题目描述
# 多重背包问题 I ## 题目描述 有 $N$ 种物品和一个容量为 $V$ 的背包。 第 $i$ 种物品最多有 $s_i$ 件，每件物品的体积为 $v_i$，价值为 $w_i$。 你可以从每种物品中选取若干件，选取数量必须是整数，且不能超过该种物品的数量限制。请在所选物品总体积不超过背包容量 $V$ 的条件下，求能够获得的最大总价值。 ## 输入格式 从文件 `multi.in` 读入数据。 第一行包含两个整数 $N$ 和 $V$，用空格隔开，分别表示物品种数和背包容量。 接下来 $N$ 行，每行包含三个整数 $v_i$、$w_i$ 和 $s_i$，用空格隔开，分别表示第 $i$ 种物品每件的体积、每件的价值和最多可选取的数量。 ## 输出格式 将结果输出到文件 `multi.out`。 输出一个整数，表示所选物品总体积不超过 $V$ 时能够获得的最大总价值。 ## 数据范围 - $1 \le N,V \le 100$。 - $1 \le v_i,w_i,s_i \le 100$，其中 $1 \le i \le N$。 ## 样例输入 ``` 4 5 1 2 3 2 4 1 3 4 3 4 5 2 ``` ## 样例输出 ``` 10 ``` ## 样例说明 选取第一种物品 $3$ 件、第二种物品 $1$ 件，总体积为 $3 \times 1 + 1 \times 2 = 5$，总价值为 $3 \times 2 + 1 \times 4 = 10$。 ## 运行限制 - 时间限制：$1000$ 毫秒。 - 内存限制：$64$ MB。