求解完全背包问题 ### 题目描述 实现一个算法求解完全背包问题。完全背包问题的介绍如下： - 已知一个容量为 $total\_weight$ 的背包，有不同重量不同价值的物品，问怎样在背包容量限制下达到利益最大化。 - 完全背包问题的每个物品可以无限选用 背包问题求解方法的介绍如下： - 用符号 $V_i$ 表示第 $i$ 个物品的价值，$W_i$ 表示第 $i$ 个物品的体积，$V_{i,j}$ 表示当前背包容量为 $j$ 时，前 $i$ 个物品最佳组合对应的价值。 - 对于当前第 $i$ 个商品，如果包的容量能够装下该物品，即 $W_i \leq j$。此时需要判断装或者不装这个物品的价值对比，选择使价值更大的情况，即 $V_{i,j} = \max {(V_i + V_{i - 1,j - W_i}, V_{i - 1, j})}$ ### 输入描述 第一行为两个数字 $total\_weight、N$，均不超过 1000。$total\_weight$ 含义见题干，$N$ 为物品数量。 接下来 $N$ 行，每行两个数字 $W_i$、$V_i$，均不超过 1000。含义见题干。 ### 输出描述 输出一行，为在背包容量限制下的最大化利益。 ### 输入输出样例 #### 示例 > 输入 ```txt 8 5 3 4 5 5 1 2 2 1 2 3 ``` > 输出 ```txt 16 ```