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

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

这个算法是根据这里的解决方案进行改进的，适用于大多数情况。但是，在像下面这样的情况下会失败：

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

至少有一种可能的分配方式：D1=22; D2=30，但是当前算法无法发现它。那么有没有更好的传播算法或者特定情况下更好的残留传播算法呢？

- Vitaly Margelov

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难问题，但只是弱NP难问题，除非您有大量数据，否则使用传统的动态规划方法解决它应该不成问题。如果问题无法解决，您可以使用动态规划的最终表格来确定最佳余数。

作为扩展，您可能希望偏向这样的解决方案，即使D*Ti/T不是整数，Di也比其他选择更接近该比率。您可以定义项目利润，例如|floor(D*Ti/T/Qi) - D*Ti/T|^2 - |ceiling(D*Ti/T/Qi) - D*Ti/T|^2，这有利于最优折扣更接近天花板而不是地板的项目。然后，您将解决一个背包问题（好吧，有点像，因为“利润”可以是负数），而不是子集和，但DP并没有太大变化。

- David Eisenstat