0 #1075. 01背包(二维数组)

01背包(二维数组)

偷东西(01背包)

题目描述

一个小偷拿着一个容量有限(容量设为w)的背包去商店偷东西,每个商品都有自己的体积v和价值c,并且每个商品只有一件。小偷的目的就是用这个容量有限的背包装满价值总量最大的东西。 现在给出n件商品的体积 viv_i (i从1到n) 和价值 cic_i(i从1到n)以及背包的容量w,请求出在这n件商品中用一个容量为w的背包能够拿到的商品的最大价值是多少。

输入格式

一共输入3行数据

第一行输入2个正整数 n w(n表示商品数量,w表示背包容量)

第二行输入n个正整数 cic_i(i从1到n,ci表示第i件商品的价值)

第三行输入n个正整数 viv_i(i从1到n,vi表示第i件商品的体积)

输出格式

输出一个正整数,表示这n件商品中用一个容量为w的背包能够拿到的商品的最大价值。

样例 #1

样例输入 #1

5 10
1 2 3 4 5
5 4 3 2 1

样例输出 #1

14

样例 #2

样例输入 #2

5 15
5 3 9 4 6
3 7 5 2 8

样例输出 #2

19

提示

20>=n>=1

100>=w>=50

viv_icic_i以及最后的最大价值都是在in范围内