动态规划

填满背包问题：
有6个物品，体积数组为arr，每个物品可以拿或者不拿，完全填满容量为S的背包。有无解？这是个np问题。和0-1背包是类似但不同的，可以看作装满背包问题。
DP状态转移公式推导：


DP分析.PNG

DP递归.PNG

递归效率低，考虑迭代：


DP空间换时间.PNG

DP空间换时间.PNG

DP迭代.PNG

感谢@正月点灯笼

©著作权归作者所有,转载或内容合作请联系作者
平台声明：文章内容（如有图片或视频亦包括在内）由作者上传并发布，文章内容仅代表作者本人观点，简书系信息发布平台，仅提供信息存储服务。

推荐阅读更多精彩内容