同和创作矩阵 › ›博文归档› 技术博文归档 › 查看内容

1917_算法设计例题：最优装载（贪心）

2022-5-16 18:17| 发布者: Hocassian| 查看: 52| 评论: 0|原作者: 肇庆学院ACM合集

摘要:

C:\Users\Administrator\Downloads\2019-10-12-10-14-3-89504145421600-Problem List-采集的数据-后羿采集器.html

Pro.ID

1917

Title

算法设计例题：最优装载（贪心）

Title链接

http://10.20.2.8/oj/exercise/problem?problem_id=1917

AC

645

Submit

1939

Ratio

33.26%

时间&空间限制

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)

描述

有一批集装箱要装上一艘载重量为C的轮船。其中集装箱i的重量为w_i。最优装载问题要求确定在装载体积不受限制的情况下，将尽可能多的集装箱装上轮船。

输入

输入的第一个为测试样例的个数T，接下来有T个测试样例。每个测试样例的第一行是一个非负整数n（ n ≤ 1000 ）和一个非负整数C（ C ≤ 10000 ），分别表示集装箱的个数以及轮船的载重量。接下来有n行，每行一个非负数，表示每个集装箱的重量。

输出

Description

Input

Output

对应每个测试样例输出一行，格式为"Case #: D V"，其中'#'表示第几个测试样例（从1开始计），D为轮船可以装载的集装箱数量的最大值，V为满足D最大时轮船的实际载重量。

Sample Input

‍1
5 100
20
50
120
99
30

Sample Output

Case 1: 3 100

Author

Eapink

样例输入