电子商务:计算折扣的算法

Question

我需要关于棘手问题的专家建议.

场景是:

• 电子商务网站
• 很多产品
• 很多折扣混合在这些产品上

产品由唯一的ProductID标识并具有销售价格.很经典的场景.该产品还可以有一个或多个折扣.

折扣可以是不同类型的.折扣的一个例子是:

• 在一组产品中购买两件或两件以上产品,每件产品可享受X折优惠

订单项只能获得一个折扣,因此一旦订单项打折,就无法获得其他折扣.

测试用例数据:

• 产品-1:10美元
• 产品-2:10美元
• 产品-3:50美元
• 产品-4:100美元

折扣-A:购买两件或两件以上产品可获得以下任何产品20%的优惠

• 产品-1
• 产品-2
• 产品-3
• 产品-4

折扣-B:购买产品并享受以下产品50%的折扣

• 产品-3

测试场景1:

购物篮:包含以下行项目:

• 产品-1
• 产品-3
• 产品-4

计算#1:

• 折扣-A:产品-1,产品-3,产品-4 = $ 2 + $ 10 + $ 20 = $ 32
  • =总共32美元

计算#2:

• 折扣-A:产品-2,产品-4 = $ 2 + $ 20 = $ 22
• 折扣-B:产品-3 = 25美元
  • = 22美元+ 25美元=总共节省47美元

这意味着Discount-A和Discount-B的组合将为客户提供最佳折扣.

测试场景2:

购物篮:包含以下行项目:

• 产品-3
• 产品-4

计算#1:

• 折扣-A:产品-3,产品-4 = 10美元+ 20美元= 30美元
  • =总共节省30美元

计算#2:

• 折扣-B:产品-3 = 25美元
  • =总共25美元

这意味着应用Discount-A将为客户提供最佳折扣.

---

为了计算给定篮子的最佳折扣,必须对所有产品组合和这些产品的可用折扣进行评估.

通常,每个篮子中有30-40个订单项,每个都有0-3个折扣.

基本上我一直在寻找一种有效的方法来进行这种计算.

现在我应用折扣的算法是这样的:

• 篮子上有明显的折扣
• 获取Basket中LineItems的所有唯一ProductID
• 获取这些ProductID的所有折扣
• 每个折扣(无序)
  • 如果非折扣标记的订单项满足,请应用折扣
    • 标记折扣的折扣商品

但这并不足够,因为它没有尝试不同的订单项/折扣组合.

我一直在寻找可以解决这类问题的标准化算法,但到目前为止没有任何运气.

期待您的回复 :)

Answer 1

假如说:

1. 您可以根据购物篮计算所有可用折扣
2. 每个产品只能应用一个折扣
3. 每个折扣只能使用一次

然后问题变成了一个被称为分配问题的问题,并且可以使用匈牙利算法在O(n ^ 3)中最优地求解.

如果在产品b上使用折扣a,您将需要计算包含所节省金钱的矩阵M [a,b].(如果折扣不适用,则将保存的钱设置为0.)

匈牙利算法将计算为节省最多资金的产品分配折扣的方式.

如果您没有相同数量的折扣和产品,则添加虚拟折扣(零节省)或虚拟产品(再次零节省),直到折扣数量与产品数量相匹配.