本文源于背包九講狰右，主要講述最為基本的三種背包問題，并分析彼此之間的聯(lián)系舆床，最終找到一個(gè)“通用”的思維方式棋蚌。首先會給出一個(gè)基本的解決方案，之后再思考如何“思考”出這種方案挨队。
1附鸽，01背包
有N件物品和一個(gè)容量為V的背包。第i件物品的費(fèi)用是c[i]瞒瘸，價(jià)值是w[i]坷备。求解將哪些物品裝入背包可使價(jià)值總和最大。
基本思路
因?yàn)橛蠳件物品情臭，每件有兩種選擇省撑，放或不放，以dp[i][j]表示前i件物品在體積j的背包中所獲得的最大價(jià)值俯在，得到簡單關(guān)系： <dp[i][j] = max(dp[i-1][j], dp[i-1][j-c[i]]+w[i])>, 關(guān)鍵有兩點(diǎn)：
- 如何表示子問題（dp[i][j]）
- 找到狀態(tài)方程
思維過程
最終的最優(yōu)解就是N個(gè)物品中選取M個(gè)的組合竟秫，只要找到特定的M個(gè)組合即可，這將是一個(gè)2^N的問題跷乐，問題太多肥败，此時(shí)我們換個(gè)思路（關(guān)鍵來了），原問題為1愕提，2馒稍，3...N, 最優(yōu)解為n1,n2,n3...nM, 此時(shí)我們既不知道結(jié)尾的nM，也不知道開頭的n1浅侨，那意味著我們要進(jìn)行遍歷纽谒，此時(shí)我們以結(jié)尾為例，假設(shè)他們以i結(jié)尾如输，即前i個(gè)物品所獲得的最大值鼓黔，此時(shí)再添加上限制條件j央勒，從而得到子問題---dp[i][j]。
剩下的狀態(tài)方程就顯而易見了澳化。
2崔步，完全背包
有N種物品和一個(gè)容量為V的背包，每種物品都有無限件可用缎谷。第i種物品的費(fèi)用是c[i]刷晋，價(jià)值是w[i]。求解將哪些物品裝入背包可使這些物品的費(fèi)用總和不超過背包容量慎陵，且價(jià)值總和最大眼虱。
基本思路
由于都是整數(shù)，所以每件物品的最高數(shù)目是有限制的（V/c[i]）席纽，看似“無限”的問題轉(zhuǎn)化為“有限”捏悬，如果構(gòu)造一個(gè)加長數(shù)組的話，就是01背包润梯。但是我們還有更優(yōu)的算法过牙。
思維過程
不要考慮01背包，完全當(dāng)作一個(gè)新的題目纺铭，還是先從最后的結(jié)果來推到寇钉。最優(yōu)解必然是選了m件物品，每件有一定的數(shù)量舶赔，顯然考慮組合的情況太多扫倡，換個(gè)思路，對于每件物品要么選了要么沒選竟纳，自然為了確定最后一個(gè)被選的物品我們需要遍歷撵溃，dp[i][j]表示前i件在體積j中的最優(yōu)解。狀態(tài)方程的思路任然是第i件要么在里面锥累，要么不在里面（注意這里的“在里面”意味著可以有多件缘挑，與01中的“可選”，“可不選”區(qū)分）桶略，從而dp[i][j] = max(dp[i-1][j],dp[i][j-c[i]]+w[i]).
3, 多重背包
有N種物品和一個(gè)容量為V的背包语淘。第i種物品最多有n[i]件可用，每件費(fèi)用是c[i]际歼，價(jià)值是w[i]惶翻。求解將哪些物品裝入背包可使這些物品的費(fèi)用總和不超過背包容量，且價(jià)值總和最大蹬挺。
基本思路
好吧维贺，和完全背包一模一樣它掂，轉(zhuǎn)化為01背包即可巴帮。利用2進(jìn)制可以進(jìn)行簡單的優(yōu)化剪侮，就不多講了梅桩。
<dp[i][j] = max(dp[i-1][j-k*c[i]]+k*w[i])> (0<=k<=n[i]), 當(dāng)k=1時(shí)就是01背包問題，所以01背包只是多重背包的一個(gè)特例而已，但兩者背后的“思維過程”是一致的伊履。同理，完全背包與多重背包非常類似（至于誰是誰的特例不好說）尊勿，所以二者的基本解決方案是一致的报慕。
