将“产品”组合成销售促销活动

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

每个促销活动必须有来自每个小组的一个产品，除非该项目多次出现在同一组中。促销活动可以有无限的(但通常是< 10)“套”的产品。

作为一个简单的例子，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)有没有人认为有一种更好/更快/更简单的方法来分析顾客篮子，以产生匹配的促销活动。

(二)假设我已找出最有效的方法，将货品与有关职位相匹配，那麽以甚麽方法可以以最便宜的方法来决定要记录的零售物品清单，以配合促销活动。

任何的帮助都会受到感激，因为我再也看不到隧道尽头的光明了！(最后的解决方案将在.NET中进行，我们使用server 2008 R2。)

Answer 1

在给定的购物车上检查每个促销是否有效，可以简化为最大流量。在描述我的解决方案时，我假设您能够实现并解决基于图的最大流问题。如果不是，这是第二个需要解决的问题(幸运的是，这是一个更为普遍的问题)。

让算法的输入如下：

• 一组所有有效项( I )。不一定用于算法的最终编码。
• 一个大小为C的购物车n，一个包含项目C_1 ... C_n的I的子集。因此，C = {C_i}用于i = 1...n
• 一个单一的升级P，由m子集组成，每个子集都包含一个可变的项目数。每个子集S都是I的子集。每个子集不能有重复项，但单个项可以跨多个子集出现。

按照以下方式构造一个图G：

• 添加标记为SOURCE的超级源节点
• 添加一个标记为SINK的超级接收器节点
• 对于购物车C中的每个唯一项C，添加一个可用项节点A_i，然后添加一个从SOURCE到A_i的边缘，其容量等于C中C_i出现的次数。
• 对于升级S_i中的每个子集P，添加以下内容：
  • 一个单集节点S_i，以及从S_i到SINK的一个具有容量1的边缘。
  • 对于每个必需项，I_j用于S_i，一个必需的项节点B_i_j，以及一个从B_i_j到具有容量1的S_i的边缘。

​

• 最后，对于每一对节点A_x和B_y，它们所表示的项是等价的，这是从A_x到具有容量1的B_y的边缘。

最后，运行一个以SOURCE为源，SINK为接收器的最大流算法。如果得到的最大流的值等于子集数(m)，则输出true -此购物车可以满足促销。否则输出错误-促销不能满足这个购物车。

例如，对于您的集合示例，使用购物车{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)。