#K94017. Optimize Package Loading
Optimize Package Loading
Optimize Package Loading
A delivery company needs help optimizing the loading of packages onto a truck. The truck has a weight capacity C and there are N packages with individual weights. The objective is to select a subset of packages to load onto the truck such that
\( \sum_{i\in S} w_i \le C \)
and the total weight of the loaded packages is maximized by adding packages in increasing order of weight.
For each test case, you are given the capacity C and the number of packages N, followed by a list of N weights. Your program must determine the maximum total weight that can be loaded by greedily picking the smallest weights first without exceeding the capacity, and output the result in the format "Case i: result" where i is the test case number (starting from 1).
Example:
Input: 2 50 5 10 20 30 40 10 100 3 40 50 60</p>Output: Case 1: 40 Case 2: 90
inputFormat
The input is read from standard input (stdin) and consists of multiple test cases. The first line contains an integer T, the number of test cases. Each test case begins with a line containing two integers, C (the truck's capacity) and N (the number of packages). The next line contains N space-separated integers representing the weights of the packages.
T C N w1 w2 ... wN
outputFormat
For each test case, print the result on a new line in the format Case i: X
, where i is the test case number (starting from 1) and X is the maximum total weight that can be loaded onto the truck.
2
50 5
10 20 30 40 10
100 3
40 50 60
Case 1: 40
Case 2: 90
</p>