尊重勞動成果郑现，轉(zhuǎn)載請注明
有編號為a粗梭、b、c、d、e的5件物品护戳，他們的重量分別是2首懈、2绊率、6、5究履、4滤否，他們的價值分別是6、3最仑、5藐俺、4、6泥彤，現(xiàn)在給你一個承重為10的背包欲芹，如何讓背包里裝的物品擁有最大的價值？吟吝？
一菱父、讓我們先用現(xiàn)實生活來還原一下這個場景：
去出差，襯衫剑逃、西服浙宜、領(lǐng)帶、剃須刀...都已經(jīng)裝進包里了蛹磺，手里拿著ipad在猶豫帶不帶（因為包已經(jīng)裝不下了）粟瞬？
1）第一種情況：不帶了，包就這么大萤捆，現(xiàn)在包里的東西出差就夠用了裙品！
2）第二種情況：必須要帶，因為ipad里有重要的ppt俗或，那就只能在包里預(yù)留出ipad空間市怎，看看剩下的空間怎么擺放那些必須要帶的東西！
到底怎么做才是最合理(價值最大化)蕴侣？#####
二、一些數(shù)學(xué)的東西
n代表東西的數(shù)量臭觉、c代表包的最大承重昆雀、Wi是第i件物品的重量、Pi是第i件物品的價值蝠筑、F[i,j]是最大價值(i個物品放入承重j的包)
那真實場景中的問題用數(shù)學(xué)的方式來表達狞膘，如果要求F[i,j]的最大值，則要看這兩種 狀態(tài)：
第一種情況(不帶)：F[i-1,j]
第二種情況(帶)：F[i-1,j-Wi]+Pi (j>= Wi) （在背包中給ipad預(yù)留空間Wi,剩下的i-1件物品重新擺放什乙，最后在加上ipad的價值Pi）
那什么才是最合理挽封？也就是價值最大化？那就是看這兩種情況哪種更有利于我出差臣镣！ 狀態(tài)轉(zhuǎn)換方程 ：
F[i,j] = MAX(F[i-1,j], F[i-1,j-Wi]+Pi)
是不是悟出了些規(guī)律辅愿，最大值取決于ipad裝與不裝智亮，同時也取決于之前的i-1個物品！
三点待、接下來請看看這張圖阔蛉，先明白原理
<img src="https://raw.githubusercontent.com/arkulo56/thought/master/images/algorithm/beibao.png" width="600" />
有了這張圖和上面總結(jié)的公式，我們就可以很清晰的理解01背包算法了
- e2單元格：當(dāng)只有一件物品e癞埠，包的容量是2時状原，裝不進去，所以最大值為0
- a8單元格：物品包括a苗踪、b颠区、c、d通铲、e毕莱，容量為8時，F(xiàn)[i-1,j]=F[b,8]=9测暗，F(xiàn)[i-1,j-Wi]+Pi=F[b,6]+6=9+6=15央串，兩種情況取最大值，因此這里的最大值是15
- 其他單元格依此類推...
五碗啄、代碼代碼
還沒有寫质和，稍后補充...
