背包问题的备忘录解决方法

背包问题是一个经典的动态规划问题，它的求解方法有很多，其中备忘录法是一种常见且实用的解决方法。

备忘录法的基本思路是在递归求解背包问题的过程中，将已经求解过的子问题的结果记录下来，避免重复计算，从而提高算法的效率。

具体来说，可以使用一个二维数组 memo 来记录已经求解过的子问题的结果，其中 memo[i][j] 表示在前 i 个物品中选择不超过 j 容量的最大价值。在每次递归时，先检查 memo[i][j] 是否已经计算过，如果计算过则直接返回结果，否则再进行递归求解。

递归求解的结束条件是当前物品已经全部考虑完毕，或者当前背包容量已经为 0，此时返回价值为 0。否则，如果当前物品的重量超过背包容量，则直接考虑下一个物品；否则，考虑将当前物品放入背包或者不放入背包两种情况，取其中的最大值作为当前子问题的解，并将结果记录到 memo 数组中。

最终递归求解完成后，memo[n][c] 就是在 n 个物品中选择不超过 c 容量的最大价值，即为背包问题的解。

这种备忘录法的时间复杂度为 O(n*c)，空间复杂度也为 O(n*c)。虽然比一般的递归算法要快，但仍然存在一些优化空间，比如可以使用滚动数组将空间复杂度优化到 O(c) 级别。