最优装载（贪心）

Description

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

Input

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

Output

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

Sample Input

‍1
5 100
20
50
120
99
30

Sample Output

Case 1: 3 100

 

#include<iostream>
#include<algorithm>
#include<stdio.h>
using namespace std;
int main(){
    /*
    *T表示测试用例数
    *n表示集装箱数量
    *c表示船载重量
    *w表示每个集装箱的重量
    */
    int T,n,c,c1;
    int w[1002];
    cin >> T;
    for(int i=1;i<=T;i++){
       cin >> n >> c;
       c1 = c;
      for(int j=1;j<=n;j++){
            scanf("%d",&w[j]);
        }
        sort(w+1,w+n+1);
        int k = 0;
        for(k=1;k<=n&&w[k]<=c;k++){
            c-=w[k];
        }
       cout << "Case " << i << ": "<< k-1 <<" "<< c1-c <<endl;
    }
    return 0;
}