尊重劳动成果，转载请注明
有编号为a、b、c、d、e的5件物品，他们的重量分别是2、2、6、5、4，他们的价值分别是6、3、5、4、6，现在给你一个承重为10的背包，如何让背包里装的物品拥有最大的价值？？
一、让我们先用现实生活来还原一下这个场景：
去出差，衬衫、西服、领带、剃须刀...都已经装进包里了，手里拿着ipad在犹豫带不带（因为包已经装不下了）？
1）第一种情况：不带了，包就这么大，现在包里的东西出差就够用了！
2）第二种情况：必须要带，因为ipad里有重要的ppt，那就只能在包里预留出ipad空间，看看剩下的空间怎么摆放那些必须要带的东西！
到底怎么做才是最合理(价值最大化)？#####
二、一些数学的东西
n代表东西的数量、c代表包的最大承重、Wi是第i件物品的重量、Pi是第i件物品的价值、F[i,j]是最大价值(i个物品放入承重j的包)
那真实场景中的问题用数学的方式来表达，如果要求F[i,j]的最大值，则要看这两种 状态：
第一种情况(不带)：F[i-1,j]
第二种情况(带)：F[i-1,j-Wi]+Pi (j>= Wi) （在背包中给ipad预留空间Wi,剩下的i-1件物品重新摆放，最后在加上ipad的价值Pi）
那什么才是最合理？也就是价值最大化？那就是看这两种情况哪种更有利于我出差！ 状态转换方程 ：
F[i,j] = MAX(F[i-1,j], F[i-1,j-Wi]+Pi)
是不是悟出了些规律，最大值取决于ipad装与不装，同时也取决于之前的i-1个物品！
三、接下来请看看这张图，先明白原理
<img src="https://raw.githubusercontent.com/arkulo56/thought/master/images/algorithm/beibao.png" width="600" />
有了这张图和上面总结的公式，我们就可以很清晰的理解01背包算法了
- e2单元格：当只有一件物品e，包的容量是2时，装不进去，所以最大值为0
- a8单元格：物品包括a、b、c、d、e，容量为8时，F[i-1,j]=F[b,8]=9，F[i-1,j-Wi]+Pi=F[b,6]+6=9+6=15，两种情况取最大值，因此这里的最大值是15
- 其他单元格依此类推...
五、代码代码
还没有写，稍后补充...
