ch0207-2393 Going to the Movies
描述
Farmer John is taking some of his cows to the movies! While his truck has a limited capacity of C (100 <= C <= 5000) kilograms, he wants to take the cows that, in aggregate, weigh as much as possible without exceeding the limit C. Given N (1 <= N <= 16) cows and their respective weights W_i, determine the weight of the heaviest group of cows that FJ can take to the movies.
输入
- Line 1: Two space-separated integers: C and N* Lines 2…N+1: Line i+1 contains a single integer: W_i
输出
- Line 1: A single integer that is the weight of the heaviest group of cows that can go to the movies
样例输入
1
2
3
4
5
6
7259 5
81
58
42
33
61
样例输出
提示
81+58+42+61 = 242;this is the best possible sum
来源
USACO Open 2008 Bronze
限制