1064：01背包问题

有$$N$$件物品和一个容量为$$M$$的背包。

已知第$$i$$件物品的重量是$$w_i$$，价值是$$v_i$$。

求解如何选取物品才能使装入背包的物品价值总和最大。

注意：每件物品至多选取$$1$$次！

第一行是两个正整数$$M,N$$分别代表背包的容量和物品的件数。（$$1 \le M \le 10^5，1 \le N \le 100$$）

接下来$$N$$行，每行两个正整数$$w_i,v_i$$分别表示第$$i$$件物品的重量和价值。（$$1 \le w_i,v_i \le 10^4$$）

在一行中输出装入背包的物品价值总和的最大值。

10 4

2 1

3 3

4 5

7 9

12

题单#21（动态规划之背包DP）