n 個物品、容量 W 的 0/1 背包以 DP 求解,時間與空間複雜度為何?並說明如何壓縮空間。
參考答案與解析
時間 O(nW)、空間 O(nW);若只需最佳值,可用一維陣列由大到小更新容量,空間降為 O(W)。