31

我需要关于一个棘手问题的专家建议。

场景是：

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

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

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

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

一个行项目只能获得一个折扣，因此一旦一个行项目打了折扣，就不能再享受其他折扣了。

测试用例数据：

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

折扣-A : 购买两件或多件以下产品可享受 20% 的折扣

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

折扣-B : 购买产品并获得以下产品 50 % 的折扣

  • 产品-3

测试场景一：

购物篮：包含以下订单项：

  • 产品-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 总节省

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

测试场景 2：

购物篮：包含以下订单项：

  • 产品-3
  • 产品-4

计算#1：

  • 折扣 A：产品 3、产品 4 = 10 美元 + 20 美元 = 30 美元
    • = 30 美元总节省

计算#2：

  • 折扣 B：产品 3 = 25 美元
    • = 25 美元的总节省

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

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

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

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

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

  • 篮子上的明确折扣
  • 获取购物篮中 LineItems 的所有唯一 ProductID
  • 获取适用于这些 ProductID 的所有折扣
  • For-Each 折扣（无序）
    • 如果非折扣标记行项目满足，则应用折扣
      • 将打折的订单项标记为打折

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

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

期待您的回复 ：）

4

1 回答 1

13

假如说：

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

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

您需要计算一个矩阵 M[a,b]，其中包含在产品 b 上使用折扣 a 时节省的资金。（如果不适用折扣，则将节省的金额设置为 0。）

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

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

于 2013-05-17T12:17:45.353 回答