組合，形成促銷

Question

我重新開發一個籃子用戶選擇零售產品匹配到一個或多個有效促銷遺留系統。這些促銷活動是行業標準的BOGOF（買一送一），買二送三，購買產品X和Y並獲得10％折扣等等，但都要求您可以將潛在物品列表過濾爲那些滿足這些促銷活動。

我想解決方案採取整個購物籃零售項目和分析他們在一個操作，而不是現行的方法匹配單個產品，當它是訂購。 （目前的解決方案導致不受歡迎的限制）

每個促銷都有一系列必須存在的合格產品才能觸發促銷活動。這些被佈置在組（或位置）n編號，例如：

Example "Buy two get third free" Promotion = 

| Item 1 |    | Item 1 |    | Item 2 | 
| or |    | or |    | or | 
| Item 2 |  AND  | Item 4 |  AND  | Item 6 | 
| or |    | or |    | or | 
| Item 3 |    | Item 9 |    | Item 4 | 

    Set 1     Set 2     Set 3 

每個促進必須從每個本組恰好一個產品中，除項目出現在同一組多次。該促銷活動可以具有無限制（但通常是「套」）產品。

作爲一個簡單的例子，Item 1, Item 4 and Item 6的購物籃會觸發促銷， 類似的Item 1, Item 1 and Item 2的購物籃也會觸發它。 然而，Item 1, Item 2 and Item 3的籃子不會因爲每個集合都不滿意。

除了明確檢測何時觸發促銷活動的明確方法之外，我還需要恢復該物品已匹配到的集合（位置）以處理定價的細節等。如果更昂貴（以貨幣計算）的項目在將其分配給促銷時比較便宜（等同匹配）的項目更受歡迎，那麼也是可取的。

---

希望下一部分將有助於解決方案，而不是聽起來不清楚，它會造成不必要的噪音，隨意忽視！

到目前爲止，我的最佳解決方案是在「購物籃」中爲每個零售商品 創建一個新套餐，並保存該商品滿足的促銷套餐（位置）。 即。

Item 1 satisifies sets: {1,2} 
Item 4 satisifies sets: {2,3} 
Item 6 satisifies sets: {3} 

然後我的理論是，你「檢查」是套這個列表包含在每個位置，每個位置的推廣充滿了獨特的項目。到目前爲止，我的工作示例都使用蠻力，循環或遞歸來產生所有組合集合（以上），試圖檢查是否存在唯一的組合。這非常嚴重，除了一個非常微不足道的例子，在現實世界中根本不起作用。 （這個功能將在物品添加到購物籃時實時調用，所以需要快速）

很多研究表明，二分匹配會產生一些期望的結果，但我只能找到研究文章和相當複雜的數學關於這個問題的文本。一些僞代碼或基本邏輯會很好。

---

我的兩個問題基本上都是：

1）是否有人看到一個更好/更快/更簡單的分析顧客籃生產配套的促銷方式。
2）假設我已經確定了將物品匹配到相關位置的最有效方式，那麼確定零售物品列表以記錄促銷活動的最便宜方式是什麼？

任何援助將感激地收到，因爲我不能再看到隧道盡頭的光！ （最終的解決方案將在.NET中，我們使用SQL Server 2008 R2）。

Answer 1

檢查每個促銷在給定購物車上的有效性可減少到Max Flow。在描述我的解決方案時，我假設您能夠實現並解決基於圖形的最大流量問題。如果不是這是解決的第二個問題（幸運的是更普遍的問題）。

讓輸入算法如下：

• 一組的所有有效項目I。不一定用於算法的最終編碼。
• 購物車C的大小爲n，其子集I包含項目C_1 ... C_n。因此C = {C_i}對於i = 1...n
• 單個促銷P由m子集組成，每個子集持有可變數量的項目。每個子集S是I的子集。每個子集不能有重複，但是單個項目可以存在於多個子集中。

構造的曲線圖G如下：

• 添加超級源極節點，標記SOURCE
• 添加超宿節點，在購物車C標記SINK
• 對於每個唯一的項目C_i ，添加一個可用項目節點A_i，然後添加一個邊緣從SOURCE到A_i與容量等於發生的數量ces of C_i in C。
• 對於促進P每個子集S_i，添加以下：
  • 單組節點S_i，並從S_i到SINK的邊沿與容量1。
  • 對於每個需要的項目I_j對於S_i，需要的項目節點B_i_j，以及從B_i_j到S_i的邊緣，容量爲1。
• 最後，對於每對節點A_x的和B_y，使得它們代表的項目是等價的，從A_x到B_y容量1的邊緣。

最後，運行最大流量算法，其中SOURCE作爲源，SINK作爲接收器。如果生成的最大流量的值等於子集數量（m），則輸出true - 此購物車可以滿足促銷活動。否則，輸出false - 此購物車無法滿足促銷活動。

例如，對於您所設定的例子，用購物車{1,1,4,6}，下圖應創建：

---

預計的時間複雜度，在項目的＃是n和數字的推廣子集是m：

• 圖構建：
  • 添加SOURCE和SINK - O(1)
  • 從源添加從購物車和邊緣獨特的項目 - O(N)
  • 添加之間的子集和所需項節點，邊緣 - 從子集中的節點增加邊O(N*M)
  • 下沉 - O(M)
  • 在相應項目節點之間添加邊 - O(N^2)
  • 合計 - O(N^2 + N*M) = O(N * (N+M))
• 最大流算法 - 請參閱維基頁面。簡單的實施成本 - O((N*M)^3)。可以用更復雜的算法進行改進。
• 檢索解決方案 - O(1)。