У меня есть заказ с количеством строк и скидкой, который должен быть распределен между этими линиями пропорционально стоимости линии.
Я не математик, поэтому я бы ввел эту запись, чтобы объяснить случай.Заказ имеет 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, но текущий алгоритм не может обнаружить его.Так что же лучше алгоритм распределения или лучший алгоритм распределения остатка в частности?