4292: 学习系列 —— DP42 完全背包问题（UKP unbounded knapsack problem）
[Creator : ]
Description
【完全背包】
问题的描述和 01 背包差不多。最大的区别就是完全背包问题中，物品的数量是无限的。这是完全背包和 01 背包的本质不同。【时间复杂度】
和 01 背包一样，也是 $O(NW)$。【空间复杂度】
和 01 背包一样，也是 $O(W)$。【问题描述】
设有 $n$ 种物品，每种物品有一个重量及一个价值。但每种物品的数量是无限的，同时有一个背包，最大载重量为 $M$，今从 $n$ 种物品中选取若干件，同一种物品可以多次选取，使其重量的和小于等于 $M$，而价值的和为最大。Input
第一行：两个整数，$M\ (M \leq 600)$（背包容量）和 $N\ (N \leq 30)$（物品数量）；
第 $2$ 到 $N+1$ 行：每行二个整数 $W_i\ (1 \leq W_i \leq 220),\ C_i (1 \leq C_i \leq 10^4)$，表示第 $i$ 个物品的重量和价值。
第 $2$ 到 $N+1$ 行：每行二个整数 $W_i\ (1 \leq W_i \leq 220),\ C_i (1 \leq C_i \leq 10^4)$，表示第 $i$ 个物品的重量和价值。
Output
仅一行，一个数，表示最大总价值。具体看样例输出。
Sample 1 Input
10 4
2 1
3 3
4 5
7 9
Sample 1 Output
max=12