小偷偷东西
初三 记叙文 461字 710人浏览 chineno4

小偷偷东西

问题描述

一天晚上,小偷带了一个包偷偷进入一家人家。小偷发现那人家家里东西很多,但他看中了n 个物品,这n 个物品的第i 个的体积为w i ,价值为v i

(i=1,2,„„,n ),包能容纳的物品的体积为c ,他要从这n 个物品中选出若干件放入包,使得放入包内的物品的总体积不超过c ,而总价值达到最大。 输入

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

每组测试数据有3行:其第1行上有2个整数n 和c ,分别是物品个数n 和包所能容纳物品的体积,(n<=50,c<=500),第2行上有n 个整数v 1、v 2、„、v n ,依次是n 个物品的价值,第3行上有n 个整数w 1、w 2、„、w n , ,分别是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