351. 完全背包
时间限制：1000 MS 内存限制：128 MB
题目描述
# 完全背包 ## 题目描述 有 $N$ 种物品和一个容量为 $V$ 的背包，每种物品都有**无限件**可用。 第 $i$ 种物品的体积为 $v_i$，价值为 $w_i$。你可以从每种物品中选取任意非负整数件装入背包。 在所选物品的总体积不超过 $V$ 的前提下，求能够获得的最大总价值。 ## 输入格式 从文件 `backpack.in` 读入数据。 第一行包含两个整数 $N$ 和 $V$，用空格隔开，分别表示物品种数和背包容量。 接下来 $N$ 行，每行包含两个整数 $v_i$ 和 $w_i$，用空格隔开，分别表示第 $i$ 种物品的体积和价值。 ## 输出格式 将结果输出到文件 `backpack.out`。 输出一个整数，表示所选物品总体积不超过 $V$ 时的最大总价值。 ## 数据范围 对于所有测试数据： - $1 \le N,V \le 1000$； - $1 \le v_i,w_i \le 1000$，其中 $1 \le i \le N$； - 所有输入数据均为整数； - 每种物品可选无限件。 ## 样例输入 ``` 4 5 1 2 2 4 3 4 4 5 ``` ## 样例输出 ``` 10 ``` ## 样例说明 选取 $5$ 件第 $1$ 种物品，总体积为 $5$，总价值为 $10$，达到最大总价值。 ## 时间与空间限制 - 时间限制：$1000$ 毫秒。 - 内存限制：$128$ MB。