背包算法问题

Question

背包问题只计算了最大装多少，具体装了哪些东西，怎么返回？
另外，如果我的背包容量是很大的数字，那么我初始化的memo数列不是也很大？比如说有6个物品可以用来装，背包容量有10万那么大，那我的memo数列不就是6*100000的一个二维数列

Answer 1

liuyubobobo 2017-04-16 07:07:36

在课程的9-9大致介绍了求动态规划问题的具体解的思路。可以看一看，然后尝试自己实现一下：）

对于你说的第二个问题，是这样的哦。所以在9-6，我们介绍的优化思路，都是针对空间的优化。

但是，即使如此，背包问题可能还是会有空间的限制，需要使用其他技巧来规避。比如背包虽然有10万，但6个物品的重量和远小于10万，我们就知道了可以直接把所有物品装进去。如果所有物品的重量也很大，我们可以尝试将所有物品的重量和背包的重量整体缩小一个公约数，等等等等。但如果通过各种方式，空间仍然不能满足计算条件，可能就需要思考这个问题是不是应该使用背包问题的模型来求解了。

• 提问者 JGOD #1

  非常感谢！