三種背包問題定義
01背包：有N件物品和一個(gè)容量為C的背包酿秸，第i件物品消耗的容量為Wi干旁，價(jià)值為Vi，求解放入哪些物品可以使得背包中總價(jià)值最大愤惰。
完全背包：有N種物品和一個(gè)容量為C的背包包归，每種物品都有無限件可用锨推，第i件物品消耗的容量為Wi，價(jià)值為Vi箫踩，求解放入哪些物品可以使得背包中總價(jià)值最大爱态。
多重背包：有N種物品和一個(gè)容量為C的背包，第i種物品最多有Mi件可用境钟，每件物品消耗的容量為Wi锦担，價(jià)值為Vi，求解入哪些物品可以使得背包中總價(jià)值最大慨削。
從0-1背包開始
dp[i][w] 的定義如下：對于前 i 個(gè)物品洞渔，當(dāng)前背包的容量為 w套媚，這種情況下可以裝的最大價(jià)值是 dp[i][w]。
那么dp[i][j]的最優(yōu)解從哪里來呢磁椒，只有兩種情況：要么不放第i個(gè)物品堤瘤，此時(shí)的最優(yōu)解=dp[i-1][j]；要么放浆熔，此時(shí)的最優(yōu)解=dp[i-1][j-Wi]+Vi本辐。
由于dp[i][j]的值依賴左上方的值，所以整個(gè)表本來應(yīng)該是從左到右医增，從上到下更新的慎皱。但是，其實(shí)我們只需要dp[i-1]就好了叶骨。但是在一維數(shù)組里操作會(huì)出現(xiàn)問題茫多，當(dāng)?shù)趇行的值覆蓋掉了第i-1行的值怎么辦呢？所以需要從右到左更新（只要知道dp[i-1]忽刽，dp[i]的更新順序是無所謂的）天揖。
Python代碼示例：
max_weight=int(input())
w = list(input().split(','))
v = list(input().split(','))
w = [int(each) for each in w]
v = [int(each) for each in v]
dp = [0]*(max_weight+1)
for i in range(len(w)):
# 從右向左更新
j=max_weight
while j>=w[i]:
dp[j] = max(dp[j],dp[j-w[i]]+v[i])
j-=1
print(dp[-1])
擴(kuò)展到完全背包
我們?yōu)榱双@取到上一次計(jì)算的值，我們選擇從后往前計(jì)算跪帝，但是完全背包正好相反今膊，這才是它需要的，完全背包因?yàn)樾枰塾?jì)多個(gè)同一物品的值歉甚，前一次計(jì)算可能是1個(gè)万细、2個(gè)等等扑眉，下一次j變化了以后纸泄，計(jì)算的可能是3個(gè)或者更多，所以我們需要保存實(shí)時(shí)計(jì)算出來的多個(gè)同一物品的最大價(jià)值腰素，我們選取從前往后的順序聘裁，這樣每次前面計(jì)算的我們都可以在j增大以后累加獲得更多個(gè)同一物品的最大價(jià)值。
