1.遞歸解法
遞歸解法存在大量的重複計算。導緻效率不高。下面可以進一步優化。
--------------------------------------------------------------------------------------------
2.記憶搜尋解法。
申請一個二維數組用來記錄重疊子問題。用空間換時間。
記憶搜尋雖然在時間複雜度上已經滿足要求，但是遞歸需要大量堆棧上的空間，容易造成棧溢出。最好能将遞歸轉換成遞推。
==========================================================================
3.動态規劃解法。動态規劃其實就是一個填表的過程。下面舉個例子說明整個過程。
假設有一個容量為5的背包以及3個物品
申請一個二維表格dp，并将第一行和第一列初始化。初始化的規則為。
對于第一行，第一行表示隻有一個物品。是以隻要capacity >= weights[0]，就初始化為values[0]。
對于地理列，第一清單示背包容量為0的時候，是以第一列的值都為0
然後填dp[1][1]
=======================================================================
4.空間壓縮。從填表的過程可以看出。其實每次隻依賴上一行。是以用一個2行的數組即可表示整個過程。
=================================================================
5.空間繼續壓縮。用一行也可以。
為什麼要強調遞推過程是逆序的呢？
舉個例子
假設n=1，背包容量c=5，隻有一個物品，w和v都為1，倒着推得結果為
0 1 2 3 4 5
1 0 1 1 1 1 1
正着推得結果為
1 0 1 2 3 4 5
其實正向遞推為完全背包。
因為倒着推。每個物品隻有一次選擇的機會，放或者不放。
正向推。每個物品在每次都可以選擇放或者不放。是以是完全背包。
完全背包代碼如下
一些背包問題相關的算法題解析請參考此博文