求解 01 背包问题 ### 题目描述 实现一个算法求解 01 背包问题。背包问题的介绍如下： - 已知一个容量为 $total\_weight$ 的背包，有不同重量不同价值的物品，问怎样在背包容量限制下达到利益最大化。 - 01 背包问题要求每个物品只有一个，可以选择放入或者不放入背包。 背包问题求解方法的介绍如下： - 用符号 $V_i$ 表示第 $i$ 个物品的价值，$W_i$ 表示第 $i$ 个物品的体积，$V_{i,j}$ 表示当前背包容量为 $j$ 时，前 $i$ 个物品最佳组合对应的价值。 - 对于当前第 $i$ 个商品，如果包的容量比该物品体积小，即 $j < W_i$。那么此时的价值与前 $i-1$ 个的价值是一样的，即 $V_{i, j} = V_{i - 1, j}$。 - 对于当前第 $i$ 个商品，如果包的容量能够装下该物品，即 $W_i \leq j$。此时需要判断装或者不装这个物品的价值对比，选择使价值更大的情况，即 $V_{i,j} = \max {(V_i + V_{i - 1,j - W_i}, V_{i - 1, j})}$。 通过最优解回溯法找到解的组成： - 当 $V_{i, j} = V_{i-1, j}$时，说明没有选择第 $i$ 个物品。 - 当 $V_{i, j} = V_{i - 1,j - W_i}$ 时，说明装了第 $i$ 个商品。 - 从 $i，j$ 的最大值一直遍历到 $i＝0$ ，则找到了所有解。 ### 输入描述 第一行为两个数字 $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 10 ```