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

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

该方案是:

电子商务网站

很多产品

这些产品上有很多折扣

产品由唯一的ProductID标识并具有销售价格。非常经典的场景。
该产品还可以享受一种或多种折扣。

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

在一组产品中购买两个或多个，并从每个产品中减X％

订单项只能获得一个折扣，因此，一旦对某个订单项进行了折扣，就无法再享受其他折扣。

测试案例数据:

产品-1:10美元

产品2:10美元

产品3:$ 50

产品4:100美元

折扣-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

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

为了计算给定购物篮的最佳折扣，实际上必须评估产品的所有组合以及这些产品的可用折扣。

通常，购物篮中有30-40个订单项，每个项目都有0-3的折扣。

基本上，我一直坚持寻找一种有效的方法来执行此计算。

现在，我使用折扣的算法类似于:

清除购物篮上的折扣

获取购物篮中LineItem的所有唯一产品ID

获取这些ProductID的

的所有折扣

每次折扣(无序)

如果折扣未标记的订单项满足折扣，则应用折扣

将打折的订单项标记为打折的

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

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

希望能从你那听到答复 :)

最佳答案

假如说:

您可以根据购物篮

计算所有可用折扣

每个产品只能对其应用一个折扣

每个折扣只能使用一次

然后该问题成为一个称为assignment的问题，可以使用Hungarian algorithm在O(n ^ 3)中最佳解决。

您将需要计算一个矩阵M [a，b]，其中包含在乘积b上使用折扣a时节省的钱。 (如果没有折扣，则将节省的金额设置为0。)

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

如果折扣和产品的数量不同，则添加虚拟折扣(零储蓄)或虚拟产品(再次零储蓄)，直到折扣数量与产品数量匹配为止。