问题1269--0-1背包

1269: 0-1背包

[命题人 : ]
时间限制 : 1.000 sec  内存限制 : 64 MB

题目描述

有 N 件物品和一个容量为 V 的背包。放入第 i 件物品耗费的空间是 Ci ,得到的价值是 Wi 。求解在不超过容量的前提下,将哪些物品装入背包可使价值总和最大。

输入

第 1 行两个正整数,分别表示 N 和 V,中间用一个空格隔开。
第 2 行 N 个正整数,表示 Ci ,中间用一个空格隔开。
第 3 行 N 个正整数,表示 Wi ,中间用一个空格隔开。
其中:1≤N≤100,1≤V≤106 ,1≤Ci ≤10000,1≤Wi ≤10000。

输出

一行一个正整数,表示最大的价值总和。

样例输入 Copy

4 20
8 9 5 2
5 6 7 3

样例输出 Copy

16

来源/分类