背包問題是關於最佳化的問題,要解最佳化問題可以使用「動態規劃」(Dynamic programming),從空集合開始,每增加一個元素就先求出該階段的最佳解,直到所有的元素加入至集合中,最後得到的就是最佳解。 以背包問題為例,我們使用兩個陣列value與item,value表示目前的最佳解所得之總價,item表示最後一個放至背包的水果,假設有負重量 1~8的背包8個,並對每個背包求其最佳解