Problem 2009 --胖虎搬校区（二）

2009: 胖虎搬校区（二）

上一题 正确率: $16.22\%$ 下一题
"
Time Limit $1$ 秒/Second(s) Memory Limit $512$ 兆字节/Megabyte(s)
提交总数 $37$ 正确数量 $6$
裁判形式 标准裁判/Standard Judge 我的状态 尚未尝试
难度 分类标签 动态规划

Description

刁难我胖虎，他最近又遇到麻烦了，不久就要搬到新校区了，他有很多物品（它们不可分割的），可是他只有一个袋子，他想装下最大价值的东西。我们已知每个物品的价值vi和重量wi；如果给你一个袋子它能容纳的重量W（10<=m<=20）,你所要做的就是把物品装到袋子里，使袋子里的物品的价值总和最大。
1 <= n <=100
1 <= wi <= 10^7
1 <= vi <= 100
1 <= W <= 10^9

Input

刁难我胖虎，他最近又遇到麻烦了，不久就要搬到新校区了，他有很多物品，可是他只有一个袋子，他想装下最大价值的东西。我们已知每个物品的的价值vi和重量wi；如果给你一个袋子它能容纳的重量为W,你所要做的就是把物品装到袋子里，使袋子里的物品的价值总和最大。
1 <= n <=100
1 <= wi <= 10^7
1 <= vi <= 100
1 <= W <= 10^9

Output

满足题意的最大价值，每组测试数据占一行。

Sample Input复制

4 5
2 3
1 2
3 4
2 2

Sample Output复制

7

推荐代码 查看2009 所有题解 上传题解视频得图灵币

本题记录 用 户（点击查看用户） 运行号（点击购买题解） 时 间
算法最快[$96 $ms] 纪雷 111428 2017-07-12 18:30:30
内存最少[$10120 $KB] 孙孟强 399360 2019-04-13 11:16:10
第一AC 111091 2017-07-11 12:16:27
第一挑战 111014 2017-07-11 09:57:33

赛题来源/所属竞赛 N/A

竞赛编号 竞赛名称 竞赛时间 访问比赛
1314 《 2019春季ACM/NOI高级算法集训班》训练五：动态规划 2019-03-30 12:00:00 请登录
1109 ACM暑期集训第二周测试赛 2017-07-11 09:00:00 请登录