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

Question

我需要有关棘手问题的专家建议。

场景是:

• 电子商务网站
• 很多产品
• 这些产品有很多折扣

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

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

• 购买一组产品中的两个或更多个并获得每个产品 X% 的折扣

一个订单项只能获得一个折扣，因此一旦一个订单项被打折，它就不能再享受其他折扣了。

测试用例数据:

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

Discount-A:购买两件或两件以上即可享受以下任何产品 20% 的折扣

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

Discount-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 个折扣。

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

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

• 购物篮有明显折扣
• 获取购物篮中 LineItem 的所有唯一 ProductID
• 获取这些 ProductID 的所有可用折扣
• For-Each 折扣(未排序)
  • 如果非折扣标记的订单项满足折扣，则应用折扣
    • 将打折的订单项标记为打折

但这根本不够，因为它没有尝试不同的订单项/折扣组合。

我一直在四处寻找可以解决此类问题的标准化算法，但到目前为止还一无所获。

希望收到你的来信:)

Answer 1

假设:

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

然后这个问题就变成了一个叫做 assignment 的问题问题，可以使用 Hungarian algorithm 在 O(n^3) 中得到最佳解决.

您需要计算一个矩阵 M[a,b]，其中包含如果对产品 b 使用折扣 a 所节省的钱。 (如果折扣不适用，则将节省的钱设置为 0。)

匈牙利算法将计算为最省钱的产品分配折扣的方式。

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