動態(tài)規(guī)劃鞠评，是算法初學(xué)者怎么也繞不開的大山……它分外讓人頭疼，云山霧繞聋涨，不得要領(lǐng)负乡。我感覺，它其實是一種新的思維方式茂腥，讓人學(xué)會打破常規(guī)思路去看待問題（只是我個人作為小白的不成熟的小領(lǐng)悟）最岗。
動態(tài)規(guī)劃中朝捆，有個經(jīng)典的背包問題，也被稱為0-1背包問題驯用。這個問題是假設(shè)我有一個包儒老，什么都想往里裝，但是包就這么大淘这，我想盡量裝多點值錢的東西進去，怎么辦钠怯？
這個問題看似炒雞簡單且貼近生活曙聂，但是實質(zhì)上暗藏玄機，所以就有很多種很多種解法断国。
一般來說榆苞，根據(jù)生活常識坐漏，應(yīng)該選擇先裝最貴的，但是這里有個致命的問題：如果最貴那個它體積也很大街夭，那最后綜合結(jié)果可能還不如裝單價不那么貴但可以多塞幾個的躏筏。
那然后我們就可以說，不然選取標準換成單位價值（直白點說就是性價比）埃碱，意思就是：每個貨物的價值除以它的體積乃正，這樣就可以避免只看那些雖然單價挺值錢但是大的要死的物品婶博，但是問題并沒有得到解決凡人，因為背包的容量是一定的叹阔，無論如何在放每個物品前都要考慮的是：放了這個還能不能放別的，萬一這個一個就把包裝滿了而放別的性價比低可以多塞幾個更劃算咋辦岸晦？
那怎么解決到底拿哪些物品可以達到最優(yōu)解呢？
正常人的思路都是從暴力求解法開始的启上，畢竟計算機就擅長這個，只要規(guī)則清晰明了倒慧，計算過程再復(fù)雜都不怕包券。其實每個物品都有兩種選擇：拿它，不拿付秕，這也就是0-1背包問題的由來询吴，拿了就是1，不拿就是0汰寓。那苹粟，大不了就把所有的組合都列一遍出來唄嵌削，只要最后選擇拿的物品體積之和不大于包的容量就算一個可能的組合方式，再在這些可能解里找一個最大的值肌访，看起來沒啥問題艇劫。
有問題嗎？有蟹演。最大的問題是顷蟀，物品少些還成，物品稍微多一點羞反，每加一個物品，循環(huán)就深一層是趴，時間復(fù)雜度以指數(shù)形式坐火箭一樣蹭蹭蹭往上竄膏秫。我們都知道，最壞最壞的算法窘哈，就是把時間復(fù)雜度搞成指數(shù)形式的亭敢，最好想都不要想，所以暴力求解法對背包問題來說只能是一個大大的NO让腹。
硬攻搞不定骇窍，就只能學(xué)習(xí)智取了。
上面說到腹纳，0-1背包問題翻譯一下是這樣：有一長串兒的物品清單嘲恍，每個都可以選擇取或者不取雄驹，唯一的限制就是物品總量不能超過背包限制医舆，并且物品是無法分割的。那么其實對每個物品取用狀態(tài)都會對背包的剩余容積造成影響蔬将，這是一點娃胆。還有就是里烦，假設(shè)我們是按照清單按順序去查看每一個物品的，那么輪到每個物品的時候胁黑，我們都不太需要關(guān)注前面取了什么，只需要看背包剩余容量還能不能裝漂洋，以及當前物品還要不要裝這兩件事力喷。
為什么要這么想呢？這就涉及到動態(tài)規(guī)劃一些基本的概念了贝咙。
首先要明確一點是拂募，動態(tài)規(guī)劃是個很方便的好登西，它可以把紛紛擾擾充滿無數(shù)種可能的問題（比如指數(shù)級問題）轉(zhuǎn)化為計算復(fù)雜度固定的問題蔼水，只不過需要犧牲一點兒空間來換扰恳浮（畢竟世界很難兩全其美）嘁信。它的思路呢，是化繁為簡穿剖，把我們要解決的看似有無窮選擇的復(fù)雜問題轉(zhuǎn)化為子問題的遞進解決糊余。在我個人看來贬芥，動態(tài)規(guī)劃和遞歸的思路有異曲同工之妙，只不過逼近真相的方向相反蘸劈。遞歸代碼上很簡潔明了威沫，但是不可避免地有大量重復(fù)計算，造成浪費孵构，而動態(tài)規(guī)劃可以利用起這些中間結(jié)果烟很，一步步接近真相。
只可惜恤筛，如此化繁為簡的良方叹俏，不是所有的問題都可以拿來如此這般抽絲剝繭抓住要害的粘驰。可以用動態(tài)規(guī)劃來解決的問題都必須滿足：最優(yōu)解的子問題也需要是最優(yōu)解蝌数。還有：前面做的選擇不會影響到后面的選擇度秘。第一個條件還比較好理解，因為本來動態(tài)規(guī)劃就是一步步推到最終結(jié)果的唆貌，假如前面的選擇好壞都無所謂锨咙，那最后結(jié)果還怎么保證最優(yōu)呢？第二個條件看起來稍有些迷惑——因為很顯然酪刀，上一個東西裝了可能會導(dǎo)致下一個裝不進去钮孵，這難道不算是對后面的選擇有影響嗎？答案是：不算巴席！因為每一個物品選擇裝或不裝時，它們之間都是相互獨立的荧库，我不關(guān)心前面是不是選了A物品电爹，我只關(guān)心前面所有物品占的體積，還有它們產(chǎn)生的最大價值料睛，但是不會因為有了A物品就不可以選擇B物品這樣的限制丐箩，所以這就是無后效性。
我們回到背包問題本身恤煞，就剛剛的條件而言屎勘，它滿足動態(tài)規(guī)劃的基本前提，所以可以用動態(tài)規(guī)劃來做居扒。我們需要找到它的子問題概漱，下面的話有些繁瑣，但是對于理解這個問題來說是有一些用處的：對于每一個物品而言喜喂，都有裝和不裝的選項瓤摧，假設(shè)此時問題中有5個物品，那么我們只看選到第5個物品時的情況（假設(shè)前面我們已經(jīng)選到了用這個包裝4個物品最值錢的取法）∮裼酰現(xiàn)在第五個物品擺在眼前照弥，首先想想是不是可裝：這第五個物品本身有沒有超過了背包的總?cè)萘浚咳绻^了只能直接放棄给赞；下一步如果確定可以裝，就要決定要不要裝障涯？判斷準則也很明確：裝的話需要保證這個取法更值錢（起碼跟前四個物品最佳方案一樣值錢，不然不如不裝）。
仔細想想都弹，第五個物品在背包容量足夠裝的情況下，判斷值錢的裝法框杜，就是在選它所帶來更新后的收益，和不選它的原來的收益里選一個最大值。不選它的收益专筷，就跟用這個背包裝四個物品的最優(yōu)解是一樣的，而選它的收益的計算方法是把背包里第五個物品將會占的空間去掉，剩下空間在只有四個物品時的最優(yōu)解（假設(shè)我們也知道縮小的背包裝四個物品最值錢的解法）加上第五個物品的價值莺葫。這兩種收益選其中大值堡纬，就是我們要的烤镐，用背包裝五個物品的最優(yōu)解了。
上面這一大串啰里八嗦的話就是我對背包問題子問題的理解了祟辟，如果問題就是5個物體的選擇，那么根據(jù)上面的思維過程叮喳，我們需要從算出1個物品裝進背包最優(yōu)解剩晴，推到2個趣兄，3個，4個才能一層層推出5個物體的最優(yōu)解鲁纠；同樣迄汛，因為每加入一個新的物品都可能會用到剩余空間在沒放這個物品情況下的最優(yōu)解，所以選取組合容量也必須從1開始每一個值都計算，直到到背包真實容量為止躬柬。
這就是為什么背包問題的動態(tài)規(guī)劃初始形態(tài)是填一張二維的表格，這個表格的縱軸是每個物品（應(yīng)該理解為物品的累加：1-表示可選擇的有物品1，2-表示可選擇的有物品1琼掠，2……以此類推），橫軸表示容量從1-遞增到背包的容量上限戈毒。這張表格里的每一個格子表示：在當前的容量j下冠桃，可選的物品有1碳蛋，2笤受，…i 這些身坐，此時的最優(yōu)解涯鲁。
實際的代碼中警绩，會多出一行表示當物體為0（意味著沒有物品可放）的值咧擂，和一列背包容量為0（意味著背包什么也放不了）的值贸桶，它們在0-1背包問題中默認初始值都為0旗笔。前者是為初始化撮弧，這樣放第一個物品的時候，如果背包裝不下裙椭，就等同于沒有物品可放；而后者是為了計算背包正好裝滿的時候，求剩余空間為0的最優(yōu)解，可以正確返回0。
下面獻上我很丑的代碼：
#!/usr/bin/env python
# -*- coding:utf-8 -*-
def backpack_0_1(items,capacity,weights,values):
# 初始化表格
dp = [[0 for _ in range(capacity+1)] for _ in range(items+1)]
solution = []
for i in range(1,items+1):
for j in range(1,capacity+1):
if j <weights[i-1]:
dp[i][j] = dp[i-1][j]
else:
dp[i][j] = max(dp[i-1][j],dp[i-1][j-weights[i-1]]+values[i-1])
# 返回物品選取方案
i = items
j = capacity
while i > 0:
print(i,j)
if dp[i][j] > dp[i-1][j]:
solution.append(i)
j -= weights[i-1]
i -= 1
return solution,dp[-1][-1]
print(backpack_0_1(4,10,[2,3,5,5],[2,4,3,7]))
