2838. The Eating Puzzle
Time Limit: 1.0 Seconds Memory Limit: 65536K
Total Runs: 256 Accepted Runs: 136 Multiple test files
Bessie is on a diet where she can eat no more than C (10 ≤ C ≤
35,000) calories per day. Farmer John is teasing her by putting out
B (1 ≤ B ≤ 21) buckets of feed, each with some (potentially
non-unique) number of calories (range: 1..35,000). Bessie has no
self-control: once she starts on a feed bucket, she consumes all
of it.
Bessie is not so good at combinatorics. Determine the optimal
combination of feed buckets that gives Bessie as many calories
without exceeding the limit C.
As an example, consider a limit of 40 calories and 6 buckets with
7, 13, 17, 19, 29, and 31 calories. Bessie could eat 7 + 31 = 38
calories but could eat even more by consuming three buckets: 7 +
13 + 19 = 39 calories. She can find no better combination.Input
* Line 1: Two space-separated integers: C and B
* Line 2: B space-separated integers that respectively name the number
of calories in bucket 1, 2, etc.Output
* Line 1: A single line with a single integer that is largest number
of calories Bessie can consume and still stay on her diet.Sample Input
40 6
7 13 17 19 29 31
Sample Output
39
Source: USACO December 06 Bronze
Submit List
Runs Forum Statistics
Tianjin University Online Judge v1.2.4