背包最大和

提交数: 2, 通过率: 50%, 平均分: 70

题目描述:

给出 N( N ≤ 46 ) 个物品的重量,以及一个容量为 W( 1≤W≤ 231 )的背包,求在背包容量范围内一次性能装入的最大重量。

输入格式:

第一行两个整数W 和 n。

第二行 n 个整数表示每个物品的重量,每个物品重量 1 ≤ a[i] ≤ 231

输出格式:

一个整数表示答案。

样例输入:

20 5
7 5 4 18 1

样例输出:

19

提示:

折半枚举算法

时间限制: 5000ms
空间限制: 512MB