如果你不知道什麼叫做0-1背包問題，下面是0-1背包問題的簡單描述 假設有n件物品 每件物品的體積為w1, w2……wn 相對應的價值為 v1, v2.……vn。 01背包是在n件物品取出若干件放在空間為total_weight的背包裡，使得背包的總體積最大 關於0-1背包問題沒有優化版本，請看這裡 上面的核心代碼是下面這一段 [cpp] for (int i = 1; i <= n; i++) { for (int j = 1; j <= total_weight; j++) { if (w[i] > j) { c[i][j] = c[i-1][j]; } else { if (c[i-1][j] > v[i]+c[i-1][j-w[i]]) { c[i][j] = c[i-1][j]; } else { c[i][j] = v[i] + c[i-1][j-w[i]]; } } } } 注意到狀態轉移方程 c[i][j] = max{c[i-1][j], c[i-1][j-w[i]]+v[i]} 每一次c[i][j]改變的值只與c[i-1][x] {x:1...j}有關c[i-1][x]是前一次i循環保存下來的值，因此，可以將c縮減成一維數組 狀態轉移方程轉換為 c[j] = max(c[j], c[j-w[i]]+v[i]); 並且，我們注意到狀態轉移方程，每一次推導c[i][j]是通過c[i-1][j-w[i]]來推導的，而不是通過c[i][j-w[i]] 因此，j的掃描順序應該改成從大到小 否則，第i次求c數組，必然先求的c[j-w[i]]的值(即c[i][j-w[i]])，再求c[j](即c[i][j])的值 由於j遞增,那麼狀態方程就成為下面這個樣子了 c[i][j] = max(c[i-1][j], c[i][j-w[i]]+v[i])顯然不符合題意 所以，上面的代碼變為 [cpp] for (int i = 1; i <= n; i++) { for (int j = total_weight; j >= 1; j--) { if (w[i] > j) { c[j] = c[j]; //表示第i次與第i-1次相等，這裡因為c[j]本來就保存這上一次的值，所以這裡不需變化 } else { //說明第i件物品的重量小於背包的重量，所以可以選擇第i件物品放還是不放 if (c[j] > v[i]+c[j-w[i]]) { c[j] = c[j]; } else { c[j] = v[i] + c[j-w[i]]; } } } } 最後我們可以做下優化，把不必要的語句去掉即可完成優化 [cpp] for (int i = 1; i <= n; i++) { for (int j = total_weight; j >= w[i]; j--) { if (c[j] <= v[i] + c[j-w[i]]) c[j] = v[i] + c[j-w[i]]; } } 如此優美的代碼簡直無法想象! 注意，空間優化版本最後是求解不出來最優解序列的，但是能求出最優解，也就是最大價值
