【問題K08】背包問題(knapsack)。            [回前頁]

在動態規劃中，背包問題、最短路徑…是常被提到的問題：

假想有一個小偷要偷保險箱內的東西。其中有N種不同大小和價值不同的東西可偷，但是他只有一個大小容量為M的小背包可把東西搬走。"背包問題"便是找出這個小偷該偷些什麼，裝入他的背包中，以使偷到的東西價值最多。

比如，他的背包容量是17，而保險箱中有許多東西，其大小和價值如圖所示：那麼這個小偷可以拿5個A, (A的價價是4，體積是3)。(6個就不行了, 因為6*3=18>17)，總共價值20；或者他可以把DE塞入背包中，總共價值24；或者他還可以其他方式，但怎麼最多價值呢？請設法解決這個問題。