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