350. 01背包问题
时间限制：1000 MS 内存限制：64 MB
题目描述
# 01背包问题 ## 题目描述 有 $N$ 件物品和一个容量为 $V$ 的背包。每件物品最多只能使用一次。 第 $i$ 件物品的体积为 $v_i$，价值为 $w_i$。 你可以选择若干件物品装入背包，使所选物品的总体积不超过 $V$。求所选物品总价值的最大值。 ## 输入格式 从文件 `knapsack.in` 中读入数据。 第一行包含两个整数 $N$ 和 $V$，用空格分隔，分别表示物品数量和背包容量。 接下来 $N$ 行，第 $i$ 行包含两个整数 $v_i$ 和 $w_i$，用空格分隔，分别表示第 $i$ 件物品的体积和价值。 ## 输出格式 将答案输出到文件 `knapsack.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 ``` ## 样例输出 ``` 8 ``` ## 样例说明 选择第 $2$ 件和第 $3$ 件物品，总体积为 $2+3=5$，总价值为 $4+4=8$，这是可以获得的最大总价值。 ## 时间与内存限制 - 时间限制：$1000$ 毫秒。 - 内存限制：$64$ MB。