背包算法问题
来源：9-5 0-1背包问题
JGOD
2017-04-16
背包问题只计算了最大装多少，具体装了哪些东西，怎么返回？
另外，如果我的背包容量是很大的数字，那么我初始化的memo数列不是也很大？比如说有6个物品可以用来装，背包容量有10万那么大，那我的memo数列不就是6*100000的一个二维数列
写回答
1回答
-
在课程的9-9大致介绍了求动态规划问题的具体解的思路。可以看一看，然后尝试自己实现一下：）
对于你说的第二个问题，是这样的哦。所以在9-6，我们介绍的优化思路，都是针对空间的优化。
但是，即使如此，背包问题可能还是会有空间的限制，需要使用其他技巧来规避。比如背包虽然有10万，但6个物品的重量和远小于10万，我们就知道了可以直接把所有物品装进去。如果所有物品的重量也很大，我们可以尝试将所有物品的重量和背包的重量整体缩小一个公约数，等等等等。但如果通过各种方式，空间仍然不能满足计算条件，可能就需要思考这个问题是不是应该使用背包问题的模型来求解了。
012017-04-28
相似问题