#996. 背包问题
背包问题
问题描述
有 N 个物品,第 i 个物品的重量为 Wi。现在想将一些物品装入到一个背包里,背包的最大载重量为 M。
问:能装入背包的物品的总重量最大是多少?
输入格式
第一行:两个整数 M、N;
接下来 N 行:每行一个整数 Wi。
输出格式
一个整数,表示答案。
输入样例
10 3
3
4
5
输出样例
9
数据范围
20% 的数据:1 ≤ N ≤ 10
100% 的数据:1 ≤ N ≤ 48, 1 ≤ M, Wi ≤
有 N 个物品,第 i 个物品的重量为 Wi。现在想将一些物品装入到一个背包里,背包的最大载重量为 M。
问:能装入背包的物品的总重量最大是多少?
第一行:两个整数 M、N;
接下来 N 行:每行一个整数 Wi。
一个整数,表示答案。
10 3
3
4
5
9
20% 的数据:1 ≤ N ≤ 10
100% 的数据:1 ≤ N ≤ 48, 1 ≤ M, Wi ≤ 231−1