小偷偷东西

发布时间: 2017年6月19日 00:24   时间限制: 1000ms   内存限制: 128M

一天晚上,小偷带了一个包偷偷进入一家人家。小偷发现那人家家里东西很多,但他看中了n个物品,这n个物品的第i个的体积为wi,价值为vii=1,2,……,n),包能容纳的物品的体积为c,他要从这n个物品中选出若干件放入包,使得放入包内的物品的总体积不超过c,而总价值达到最大。

输入有若干组测试数据(不超过20)

每组测试数据有3行:其第1行上有2个整数nc,分别是物品个数n和包所能容纳物品的体积,(n<=50,c<=500),第2行上有n个整数v1v2vn,依次是n个物品的价值,第3行上有n个整数w1w2wn,,分别是n个物品的重量。诸整数之间用一个空格分开。

现对输入中的每组测试数据,输出1行:先输出“Case #:”,其中“#”是测试数据的组号(从1开始)。接着输出包能装的物品的最大价值。

复制
3 4
1 3 4
3 1 4
5 10
6 3 5 4 6
2 2 6 5 4
Case 1:4
Case 2:15
1753

old_judge

old_judge_None