01背包问题－通俗易懂

尊重劳动成果，转载请注明

github地址：
https://github.com/arkulo56/thought/blob/master/software/algorithm/%E7%AE%97%E6%B3%95---01%E8%83%8C%E5%8C%85%E9%97%AE%E9%A2%98.md

---

有编号为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背包算法了

1. e2单元格：当只有一件物品e，包的容量是2时，装不进去，所以最大值为0
2. 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
3. 其他单元格依此类推...

五、代码代码

还没有写，稍后补充...