01背包是一类经典的DP问题，其特点是每种物品只有一个，只考虑选还是不选。这类问题解决的思路是计算每种背包容量，从而推得结果。考虑一个物品的时候，分两种情况：能放下和放不下，当能放下时要考虑是否放当前物品——放当前物品价值不一定更大（要知道i-1个物品只是固定了个数但不是固定了组合）；当然放不下的时候就简单了——和i-1个物品时获得的价值相同。

有一个总容量为v的背包，有n个物品，每个物品的重量分别是w_i，价值分别是c_i，问，最多能装入价值多少的物品。

第一行，有单个空格分隔的的两个整数，分别表示v和n。

接下来n行，每行有单个空格分隔的两个整数，分别表示一个物品的重量w_i和价值c_i。

对于100%的数据：

1\le v \le 1000；

1\le n,w_i,c_i \le 100。

一行，一个整数，表示能装的最大价值。

这类问题的思考方式是：按照背包容量从1-v进行考虑，所以也可以用递归的形式进行解答，其参数为当前物品编号和当前背包大小。如果要提高效率，避免重复搜索，可以用一个数组（二维）记录中间结果。