algorithm - 如何在订单行上按比例分配折扣？

Question

我有一个订单，其中包含订单数量和折扣，需要根据订单成本按比例在这些订单之间分配。

我不是数学家，所以我会引入这个符号来解释这种情况。一个订单有 N行，项目价格为 Pi , 商品数量为 Qi ，总线路成本为 Ti其中 Ti = Qi * Pi .订单总价为T = sum(Ti) .算法需要分配折扣D ，结果是 Di 的列表- 为每个订单行分配折扣。 结果必须满足以下条件:

• D = sum(Di) : 线折扣总和必须等于原始折扣
• Di%Qi = 0 : 折扣必须能整除数量而没有余数
• Di <= Ti : 折扣不得超过总线路成本
  • Di/D ~ Ti/T : 折扣尽可能按比例分配

输入数据满足以下谓词:

• D <= T , 折扣不超过总订单成本
• D , Di和 Qi是整数值，Pi是十进制数
• 输入数据的变化不能满足要求的条件。例如，3 行，每行有 3 个商品，价格为 10，输入折扣为 10 (N=3; Qi=3; Pi=10; D=10)。没有办法将它分配给行数。对于这种情况，算法应该返回错误以及无法分配的折扣金额(对于我的示例，它是 1)

现在我们的算法实现看起来像这样(F# 上的简化版本)

type Line = {
  LineId: string
  Price: decimal
  Quantity: int
  TotalPrice: decimal
  Discount: decimal
}

module Line =
  let minimumDiscount line =
    line.Quantity
    |> decimal
    |> Some
    |> Option.filter (fun discount -> discount <= line.TotalPrice - line.Discount)

  let discountedPerItemPrice line = line.Price - line.Discount / (decimal line.Quantity)

let spread discount (lines: Line list) =
  let orderPrice = lines |> List.sumBy (fun l -> l.TotalPrice)
  let preDiscountedLines = lines |> List.map (fun line ->
    let rawDiscount = line.TotalPrice / orderPrice * discount
    let preDiscount = rawDiscount - rawDiscount % (decimal line.Quantity)
    {line with Discount = preDiscount})

  let residue = discount - List.sumBy (fun line -> line.Discount) preDiscountedLines

  let rec spreadResidue originalResidue discountedLines remainResidue remainLines =
    match remainLines with
    | [] when remainResidue = 0m -> discountedLines |> List.rev |> Ok
    | [] when remainResidue = originalResidue -> sprintf "%f left to spread" remainResidue |> Error
    | [] -> discountedLines |> List.rev |> spreadResidue remainResidue [] remainResidue
    | head :: tail ->
      let minimumDiscountForLine = Line.minimumDiscount head
      let lineDiscount = minimumDiscountForLine
                           |> Option.filter (fun discount -> discount <= remainResidue)
                           |> Option.defaultValue 0m
      let discountedLine = {head with Discount = head.Discount + lineDiscount}
      let discountedLines = discountedLine :: discountedLines
      let remainResidue = remainResidue - lineDiscount
      spreadResidue originalResidue discountedLines remainResidue tail

  spreadResidue residue [] residue preDiscountedLines

该算法采用了找到的一些解决方案 here并且适用于大多数情况。 然而，它在以下情况下失败:

P1=14.0; Q1=2;
P2=11.0; Q2=3;
D=52

至少有一种可能的分布:D1=22; D2=30 ，但目前的算法未能发现它。那么什么是更好的传播算法或更好的传播残差算法？

Answer 1

让我们将 Di/D ~ Ti/T 解释为 Di ∈ {Qi*floor(D*Pi/T), Qi*ceiling(D*Pi/T)}。然后我们可以将这个问题解决为子集和，即，对于每个 i 使得 D*Ti/T/Qi 不是整数，并且 Qi*ceiling(D*Pi/T) ≤ Pi，我们有一个重量为Q_i的元素，目标总和为D - sum_i Q_i*floor(D*Pi/T)。子集和是 NP 难的，但很弱，除非你有大量的东西，否则使用传统的动态程序解决它应该没有问题。如果问题不可行，您可以使用动态程序的最终表来找出最佳余数。

作为扩展，您可能想要支持以下解决方案，尽管 D*Ti/T 不是整数，但 Di 比替代方案更接近该比率。您可以定义项目利润，如 |floor(D*Ti/T/Qi) - D*Ti/T|^2 - |ceiling(D*Ti/T/Qi) - D*Ti/T|^2 偏好最优折扣更接近上限而不是下限的商品。然后，您正在解决背包问题(好吧，有点，因为“利润”可能是负数)而不是子集和，但 DP 变化不大。