P83079

最大价值背包

难度 5 级 初三 动态规划入门 背包
讨论 统计 16通过 31提交 51.6%通过率 旧版界面
时间限制 1 秒 内存限制 128 MB

题目描述

有n种物品,第i种物品的重量和价格为wi、vi。每种物品数量无限。背包最大载重量为C。问如何放置物品,可使背包内物品价值之和最大。注意,背包不一定装满。

输入

第一行两个正整数n和C。 第二行为n个正整数wi, i=1,2,...,n。 第三行为n个正整数vi, i=1,2,...,n。

输出

背包所能容纳物品的最大价值。

样例

样例 1
输入
4 11
2 3 5 7
1 5 2 4
输出
9

提示

对于100%的数据,1\le n\le 100000, 1\le C\le 100000, 1\le w_i\le 10000,1\le v_i\le 10000。

来源

动规专题

Tab 缩进 · 提交后可在下方查看评测状态
请先登录后再提交