4291: 学习系列 —— DP41 01背包问题（0-1 knapsack problem）
[Creator : ]
Description
【什么是 01 背包问题】
01 背包问题，一般是给 $N$ 件物品，$W$ 的背包总容量，求不超过总容量 $W$ 的前提下能获得最大价值。第 $i$ 件物品的重量为 $w_i$，价值为 $v_i$。同时每个物品只有一件，我们只能选择或者不选择。
假设当前背包内所有物品的总价值为 $\text{dp[j]}$。这样对于第 $i$ 件物品，我们可以选择或者不选择。当然选择的前提是不能操作背包总容量 $W$。
对于第 $i$ 件物品，如果我们不选择。对应背包内的总价值是 $\text{dp[j]}$。
对于第 $i$ 件物品，如果我们选择。我们将增加 $w_i$ 的重量，获得了 $v_i$ 的价值。
【时间复杂度】
$O(NW)$。
【空间复杂度】
$O(W)$。
【问题描述】
一个旅行者有一个最多能装 $M$ 公斤的背包，现在有 $n$ 件物品，它们的重量分别是 $W_1$，$W_2$，...,$W_n$，它们的价值分别为 $C_1$，$C_2$，...，$C_n$，求旅行者能获得最大总价值。
01 背包问题，一般是给 $N$ 件物品，$W$ 的背包总容量，求不超过总容量 $W$ 的前提下能获得最大价值。第 $i$ 件物品的重量为 $w_i$，价值为 $v_i$。同时每个物品只有一件，我们只能选择或者不选择。
假设当前背包内所有物品的总价值为 $\text{dp[j]}$。这样对于第 $i$ 件物品，我们可以选择或者不选择。当然选择的前提是不能操作背包总容量 $W$。
对于第 $i$ 件物品，如果我们不选择。对应背包内的总价值是 $\text{dp[j]}$。
对于第 $i$ 件物品，如果我们选择。我们将增加 $w_i$ 的重量，获得了 $v_i$ 的价值。
【时间复杂度】
$O(NW)$。
【空间复杂度】
$O(W)$。
【问题描述】
一个旅行者有一个最多能装 $M$ 公斤的背包，现在有 $n$ 件物品，它们的重量分别是 $W_1$，$W_2$，...,$W_n$，它们的价值分别为 $C_1$，$C_2$，...，$C_n$，求旅行者能获得最大总价值。
Input
第一行：两个整数，$M$（背包容量，$M≤1000$）和 $N$（物品数量，$N≤1000$）；
第二到 $N+1$ 行：每行二个整数 $W_i,\ C_i, (0<W_i,\ C_i\leq 1000)$，表示第 $i$ 个物品的重量和价值。
第二到 $N+1$ 行：每行二个整数 $W_i,\ C_i, (0<W_i,\ C_i\leq 1000)$，表示第 $i$ 个物品的重量和价值。
Output
仅一行，一个数，表示最大总价值。
Sample 1 Input
10 4
2 1
3 3
4 5
7 9
Sample 1 Output
12
我们在背包中放入第 $2$ 件和第 $4$ 件物品。此时，背包总重量为 $3+7=10$，总价值为 $3+9=12$。没有比这样更好的组合。
Sample 2 Input
5 4
1 2
2 4
3 4
4 5
Sample 2 Output
8
我们在背包中放入第 $2$ 件和第 $3$ 件物品。此时，背包总重量为 $2+3=5$，总价值为 $4+4=8$。没有比这样更好的组合。