动态规划

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

DP分析.PNG
DP递归.PNG

递归效率低，考虑迭代：

DP空间换时间.PNG
DP空间换时间.PNG
DP迭代.PNG

感谢@正月点灯笼