1、省錢攻略基礎之“了解平台紅包使用規則”
規則一：紅包大類别分為“商品紅包”、“疊加券”、“郵費紅包”三種。
規則二：每個SKU（同一個商品ID），商品紅包、疊加券、郵費紅包最多每種使用一張。
規則三：商品紅包和疊加券都有可能設定使用門檻金額，門檻金額是商品促銷優惠後金額（如果有促銷），郵費紅包使用門檻基于商品紅包和疊加券優惠後金額計算。
規則四：門檻金額高的紅包優惠不一定高于門檻低的（雖然大機率如此）。
規則五：絕大多數紅包都有使用限制條件，與商品相關的：分類、歸屬的業務、賣家、包含的服務、特定的商品範圍、商品釋出時間；與場景相關：終端類型、賣場；與買賣家相關：是否是“新客戶”、買賣家是否被風控等等。
規則六：商品紅包和疊加券小類分為：滿額減和滿額折，其中滿額折紅包又有最大優惠金額如滿10元8.8折最多優惠1000元，此時如果商品10000元最多也隻能減1000元；郵費紅包分為定額紅包和免郵紅包。
2、舉個栗子
在開始計算最大優惠前，我們先舉個例子具象化實際場景，此處忽略“規則五”計算過程，直接給出符合紅包使用限制的商品與紅包關系；由于郵費紅包門檻金額基于商品紅包和疊加券後金額較為複雜，且不影響最優紅包解題思路，此處忽略郵費紅包，僅以商品紅包為例。
場景如下：
5個商品分别為：P1=10元、P2=20元、P3=30元、P4=40元、P5=50元。
5個商品紅包：R1=滿10元減5元、R2=滿20元減12元、R3=滿30元減10元、R4=滿90元減60元、R5=滿100元減80元。商品與紅包的關系如下表格:
3、最優紅包組合計算方法進化過程
3.1、初代“笛卡爾乘積”版
首先，将每個紅包的可用商品聚合：
R1->P2、P3、P4、P5 R2->P1、P3、P4、P5 R3->P1、P2、P4、P5 R4->P1、P2、P3、P5 R5->P1、P2、P3、P4
将每個紅包的可用商品進行排列組合得到下表（黃色為該組合不符合紅包門檻）：
将上表改寫成矩陣：
計算縱列笛卡爾積：
計算各組合紅包的優惠情況，按紅包優惠金額倒序，取紅包最大優惠組合情況， 得到：P5商品使用R2;P1P2P3P4使用R5，得到最大優惠金額80+12=92元。
該版本核心思想：計算出所有商品使用紅包的組合情況，并行計算各組合的優惠金額，按優惠金額倒序取最大優惠。存在的問題：商品和紅包數量增加時組合數呈指數級增長，計算笛卡爾積時很容易OOM。
3.2、二代“邊算邊比較Map聚合”版
一代算法最大的問題是将所有組合全部排列好後再進行價格計算和比較，導緻記憶體占用過大；二代算法核心思想是“邊排列組合邊計算邊比較”保留最優解，計算耗時到達規定門檻值時停止，取已算組合中的最優。這一代算法中，用到了HashMap作為記錄商品使用紅包的标記指針，資料結構如下：
//用于記錄每個商品上，各大類可用紅包的清單
private Map<ERedMetaBigType, List<RedBaseInfoInput>> prodRed = Maps.newHashMap();
//用于記錄該商品在各大類紅包清單List<RedBaseInfoInput>上使用紅包的清單index位置
private Map<ERedMetaBigType, Integer> pointer = Maps.newHashMap();
指針移動抽象示例（黃色為此輪組合指針位置）：
移動一次指針就形成一個新的組合，根據根據标記将使用相同紅包的商品“聚合” 如組合2：R5<P1,P2,P3,P4> R3
//使用Map結構記錄
Map<ERedMetaBigType, Map<Long, List<EngineInput>>> oneType2RedId2Prods = Maps.newEnumMap(ERedMetaBigType.class);
優點：不需要将所有組合都排列出後再計算比較，超過規定時間可以中斷降級處理。缺點：每次移動指針後，都需要使用Map結構将紅包商品重新“聚合”後才能計算紅包門檻和優惠，頻繁生産銷毀Map和List對象，GC壓力大。
3.3、三代“邊算邊比較數組索引定位”版
三代主要通過資料結構與虛拟邏輯關系，減少上一代算法大量生成中間臨時Map導緻GC壓力大問題。使用數組Long[] infoArray存儲商品清單，此時infoArray數組下标就含有了商品ID的含義，同理，Long[] redArray存儲紅包清單，redArray數組下标就含有了紅包ID的含義。使用byte[][] infoRedRel二維數組用于存儲商品紅包關系，數組值0表示此輪計算未使用，1表示此輪計算使用，-1表示該商品不可使用此紅包。關系數組如下：
擁有這個二維數組後，就可以通過修改這個位數數組的值（不包含-1不可用的），實作紅包使用組合的變更。
此時聚合商品不再需要使用Map生成新的結構存儲，隻需要周遊紅包清單數組，根據數組下标去infoRedRel維數組中擷取數組值，然後去infoArray取商品即可。
4、總結
本文簡述了最優紅包組合的整體演進，下表是二代和三代在不同紅包總量、商品數量、商品可用紅包數量時，200ms完成計算組合數的情況對比（30次均值）如下圖：
通過二代三代的對比，我們不難發現，在面對大量計算時除了要注意JVM記憶體使用情況外（一代FullGC或溢出），還需要關注對象生成銷毀的數量與頻率，因為在面臨大量計算時對象生成和GC也将成為性能瓶頸，三代相較二代，完成計算的組合數在5倍以上，這其間的差距都是因為二代Map對象的生成和銷毀。
關于作者
馬寶山， 轉轉交易中台Java開發工程師
來源-微信公衆号:轉轉技術
出處:https://mp.weixin.qq.com/s/AU7Ou97SfhQrlBj3zXLYyg