昨天說最優惠演算法被主播砍掉了。砍掉之前,它值得一次誠實的複雜度鑑定——答案分三層,而且最深的一層跟複雜度無關。

岔題,但值得:它到底是不是 NP-hard?

第一層:單一商品、單一價格——這是無界背包,不是 NP-hard。 把問題寫出來:客人下單付費 n 件;「買 aᵢ 送 bᵢ」每套用一次,用掉 aᵢ 件付費商品、額外多送 bᵢ 件;每件付費商品只能被一個優惠算一次。目標是最大化送出件數 Σbᵢxᵢ,限制 Σaᵢxᵢ ≤ n。這是無界背包(找零錢問題的親戚):形式上 weakly NP-hard,但有 O(n×k) 的 DP——n 是購買件數,現實裡是幾十,瞬間解完。有趣的是,greedy 在這個最簡單的情境就已經不是最優。拿「買 3 送 2」和「買 5 送 3」來算,greedy 依主播的順序先套大的:

• n=8:買 5 送 3(用掉 5 件)+ 剩 3 件套買 3 送 2——送 5 件;最優也是 5。打平。
• n=9:greedy 套買 5 送 3、再套買 3 送 2,剩 1 件閒著——送 5 件;最優是買 3 送 2 套三次——送 6 件。

greedy 輸的原因跟找零錢一樣:送得大方的優惠,「每付一件的送率」不一定高——買 5 送 3 的送率是 3/5=60%,買 3 送 2 是 2/3≈66.7%,而勝負常常取決於尾數(那 1 件掛空的付費商品)。所以精確地說,當年的 greedy 從來不是「近似最優」,它就是「規則簡單」——而這正是它被選中的理由,不必替它冠上最優的名。

而 DP 解這題有多便宜?設 f(j) 為用 j 件付費商品的額度最多能送幾件:

f(j) = max( f(j-1),  max{ f(j-aᵢ) + bᵢ : aᵢ ≤ j } ),   f(0) = 0

答案是 f(n),時間 O(n×k)。拿 n=9 走一遍:

f(9)=6,正是「買 3 送 2 套三次」。但這張表藏著一個更重要的觀察:看 f(5)→f(6)——最優組合從「買 5 送 3」整組換成「買 3 送 2 × 2」。客人多加一件商品,螢幕上的優惠組合整個重排。DP 給你最優值,但最優解的組合會隨 n 跳動——這是最優性本身的性質,跟用什麼演算法無關。 可解釋性的問題,DP 解不掉:就算計算免費,當年砍掉最優解仍然是對的。

第二層:同一件商品有好幾種價格——「最優」的定義開始漂。 商品有直播價、商城價、style 各自的價格,cart item 上還有一個「特殊價」欄位給特殊優惠用——同一台購物車裡,同一件商品可能多種價格並存。優惠套下去,免的是哪一件?扣除額按哪個價算?當年沒有明確定義「哪個價一定最便宜」——此時最優解演算法最脆弱的地方不是算力,是規格:連「最優」都沒有唯一定義,演算法是在最佳化一個沒有人簽名的目標函數。而且未定義不只讓答案漂,它讓空間爆炸:在優化器眼裡,每個未定義處都是一個變數——m 種價格解讀 × n 件商品,就是 m^n 種世界,每一種世界還要各自解一次分組最優再互比。規格少寫一句話,搜尋空間就多乘一倍;greedy 按順序套用,本質是用定義消滅變數——順序是常數、每步規則是常數,空間坍縮成一條直線。它省的不是 CPU,是規格債。

第三層:跨商品的組合,才是 NP-hard 真正的門檻。 常規的多件優惠不跨商品,券又跟非券互不影響(獨立兩層)——所以常規問題其實整個可解。但 admin 實驗層的花式買 A 送 B 一旦跨商品,加上「每件只能被佔用一次」的互斥,問題就變成 weighted set packing:從所有可能的「優惠應用」(每個是一組帶權的商品集合)裡選出互不重疊的組合、最大化總折扣——strongly NP-hard,沒有 DP 可救。當年「應該是 NP-hard」的直覺,對的就是這一層。

「還能不能 DP」其實有一條好記的判準:看新條件問的是「多少件」還是「是哪幾件」。 只改變數量或金額的條件,DP 加一維就活(滿額門檻是這類);開始需要知道「是哪幾件」的條件(送最便宜、每件有自己的特殊價、跨商品綁定),單位失去可互換性,狀態就壓不動了——DP 死於異質性,不是死於規則數量。而工程上的死亡通常更早:每個新條件都逼你重新設計狀態、重新證明正確性,在理論宣判之前,維護成本已經先執行了死刑。

三層看完,greedy 各贏一次:第一層它輸最優、贏簡單;第二層它用順序定義了語意——「按順序、每次最大扣除」同時回答了「怎麼算」和「算什麼才算對」,在價格語意模糊的地方,過程就是規格;第三層它讓花式優惠不會把整台購物車捲進組合爆炸。所以砍掉最優解的理由,按重要性排序是:解釋不動 > 定義不清 > 算不動——算力反而是最不重要的那一個。

明天講通知系統——兩個欄位、一支排程,和一通電話。

本文改寫自我的部落格系列《Re:從零開始做直播代購電商平台》,本篇完整版:https://blog.aidan.tw/blog/rezero-promotion/