在上一篇《9.動態(tài)規(guī)劃（2）——子集和問題》中，談到了什么是子集和問題，以及實(shí)現(xiàn)。背包問題實(shí)際也是子集和問題的一種，不過背包問題不是“判斷問題”而是一個(gè)“最優(yōu)問題”。而背包問題實(shí)際上又分為“0-1背包”，“完全背包”，本文對“0-1背包”進(jìn)行講解。
問題：有n個(gè)物品，每個(gè)物品的重量為weigh[i]，每個(gè)物品所對應(yīng)的價(jià)值為price[i]，現(xiàn)在有一個(gè)背包，背包所能承受的重量為W，問背包能裝下的物品總價(jià)值最大是多少？
定義s[i, j]表示前i個(gè)物品的總價(jià)值，j為背包的承重量。當(dāng)j = W或者最接近于W且小于W時(shí)，此時(shí)就是問題的解。
