问题1232--0-1 背包

1232: 0-1 背包

时间限制: 1 Sec  内存限制: 64 MB
提交: 34  解决: 10
[提交] [状态] [讨论版] [命题人:]

题目描述

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

输入

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

输出

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

样例输入 Copy

4 20
8 9 5 2
5 6 7 3

样例输出 Copy

16

来源/分类