h308. 背包装书

题目描述

有 $n$ 本书，第 $i$ 本书的重量为 $w_i$，价值为 $v_i$。背包容量为 $C$，每本书最多选择一次。

求总重量不超过 $C$ 时能够获得的最大总价值。

输入格式

第一行输入两个整数 $n,C$。

接下来 $n$ 行，每行输入两个整数 $w_i,v_i$。

输出格式

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

数据范围

• $1\le n\le 100$
• $1\le C\le 10000$
• $1\le w_i\le C$
• $0\le v_i\le 10000$

样例

4 8
3 5
4 6
5 10
2 4

15

标签：动态规划、0/1 背包