小偷偷东西

【#文档大全网# 导语】以下是®文档大全网的小编为您整理的《小偷偷东西》，欢迎阅读！

小偷偷东西

问题描述

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

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

输入

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

每组测试数据有3行：其第1行上有2个整数n和c，分别是物品个数n和包所能容纳物品的体积，（n<=50,c<=500），第2行上有n个整数v1、v2、„、vn，依次是n个物品的价值，第3行上有n个整数w1、w2、„、wn,，分别是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

本文来源：https://www.wddqxz.cn/15411a0c0640be1e650e52ea551810a6f524c81f.html