Responsive image

问题 1130 --01背包

1130: 01背包

时间限制: 1 Sec  内存限制: 128 MB
提交: 145  解决: 55
[提交][状态][讨论版][命题人:]

题目描述

有n个物品，要将它放入容量为v的背包。给出第i个物品的大小c和价值w，求出能放入背包的物品的总价值最大值。

输入描述

有多组测试数据。

每组测试数据第一行为2个正整数，分别代表背包的大小v和物品的个数n。

接下来的n行，每行2个正整数，用空格隔开，分别代表物品的大小c和价值w。所有输入数字的范围大于等于0，小于等于1000。

输出描述

对每组测试数据输出一个整数，代表能放入背包的物品的总价值。

样例输入

3 3
1 1
2 1
3 1

样例输出

2

来源

11级侯少琼 

[提交][状态]
ACM算法攻关部