问题陈述
有 N 个物品,编号为 1,2,…,N 。对于每个 i(1≤i≤N),物品 i 的重量为 wi ,价值为 vi 。
太郎决定从 N 个物品中选择一些物品装进背包里带回家。背包的容量为 W ,这意味着所取物品的重量之和最多为 W 。
求太郎带回家的物品价值之和的最大值。
限制因素
- 所有输入值均为整数。
- 1≤N≤100
- 1≤W≤109
- 1≤wi≤W
- 1≤vi≤103
输入
输入内容由标准输入法提供,格式如下:
- N W
- w1 v1
- w2 v2
- :
- wN vN
输出
打印太郎带回家的物品价值的最大可能总和。
3 8
3 30
4 50
5 60
90
应取项目 1 和 3 。那么,重量之和为 3+5=8 ,价值之和为 30+60=90 。
1 1000000000
1000000000 10
10
6 15
6 5
5 6
6 4
6 6
3 5
7 2
17
应取项 2,4 和 5 。然后,重量之和为 5+6+3=14 ,价值之和为 6+6+5=17 。
来源
https://atcoder.jp/contests/dp/tasks/dp_e