Как корректно распределить сумму внутри элементов массива?

Question

[Евгений]

Кратко. Есть заказ, внутри которого позиции товаров. У каждого есть цена, кол-во и т.д.
В некоторых заказах скидка применяется не на сам товары, а на весь заказ.
Но при работе с некоторыми платёжными шлюзами и ОФД, скидку нельзя указать на чек - приходится размазывать её по всем товарам. Вот в этом и есть проблема. Не могу найти нужный алгоритм для корректного равномерного распределения этой суммы.

По сути мне нужно discount, как то пропорционально в зависисмоти от кол-ва позиций и от кол-ва товаров в одной позиции (amount) размазать в поле price (т.е. отнять от price).

total_price - сумма заказа без скидки
total_price_final - корректная сумма заказа, которая должна быть суммой всех элементров массива (price * amount).

{
   "items":[
   "discount":3748,
   "total_price":11050.00,
   "total_price_final":7302.00,
      {
         "id":1,
         "name":"Item #1",
         "artikul":"110062600000",
         "price":10000.00,
         "amount":1
      },
      {
         "id":1,
         "name":"Item #2",
         "artikul":"110000800000",
         "price":350.00,
         "amount":6,
         "total":2100.00
      }
   ]
}

И каждый раз то сумма не сходится, то система пытается высчитать больше чем есть.
Может кто то сталкивался с похожим или есть какой то рабочий класс (алгоритм).

Comments

[res2001]

Идете в цикле по позициям, для каждой позиции вычисляете: price_final = price + discount * (price / total_price )
Дальше суммируете все price_finаl - это и будет ваша total_price_final.
price - цена конкретной позиции
total_price - цена всего заказа
price / total_price - вес конкретного товара во всем заказе - (0; 1]
discount - сумма скидки, которую надо раскидать по позициям
Если скидок несколько, то есть смысл сначала сложить все скидки в общий discount и уже расписывать его.

[Wataru]

Я правильно понимаю, что у вас числа целые? Надо целую скидку в рублях раскидать по целым ценам товаров?

Тут проблема возникает из-за разного amount у товаров. Поэтому в примере каждый рубль брошенный на второй товар - это 6 рублей скидки, так?

Можно ли вам разбивать товары из одной группы на 2? Скажем, вот у вас 6 товаров "item 2", можно ли в ответе двум из них сделать скидку 356 а четырем оставшимся - 355? Тогда в ответе будет две записи для "item 2" с разными ценами и amount 2 и 4.

Надо ли обязательно делать скидку примерно пропорционально цене товара?

[Wataru]

Евгений, вообще, а что вы ожидаете в этом случае, например?

{
   "items":[
   "discount":7,
   "total_price":530,
   "total_price_final":523,
      {
         "id":1,
         "name":"Item #1",
         "artikul":"110062600000",
         "price":100,
         "amount":5,
         "total": 500
      },
      {
         "id":1,
         "name":"Item #2",
         "artikul":"110000800000",
         "price":10,
         "amount":3,
         "total":30
      }
   ]
}

Тут дело в том, что вообще нельзя эти 7 рублей скидки раскидать по товарам в группах 5 и 3, потому что 7 нельзя представить в виде суммы троек и пятерок.

Понятно, что это вырожденный случай, но в вашей задаче должно быть как-то специфицированно, что в этом случае делать и если он невозможен, то какие возможны.

[Евгений]

Wataru, Числе не целые (исходник в вопросе поправил). Там всё в итоге приводится к копейкам - round($int, 2). По сути и разбить можно, я не вижу в этом какой то проблемы. Но идеально было бы к равномерно к каждой позиции.

Если бы товары были все в 1 штуке, то проблем не было бы. Так раньше и было. Вся сложность возникла когда появился amount :)

[Ivan Ustûžanin]

если нужно уложиться в какую-то точность (до рубля, до копейки) и скидка не кратна общему количеству товаров, то нужно всего лишь чуть увеличить скидку, например скидка была 1 ₽, а по факту получалась 1,02 ₽

[Wataru]

Евгений, Ну допустим это цены не в рублях, а в копейках. Вам надо 7 копеек раскидать по позициям в которых amount 5 и 3. Это без разбиения позиций невозможно вообще. Вам можно разбивать позиции? Можно получать скидку прмерно целевую +- несколько копеек?

[Евгений]

Wataru, да я задумался над вашим примером и понял что без разбивки позицией - это нереально. Да тогда разбивать позиции можно и даже нужно.

[Akina]

Я вообще не понимаю сути проблемы.

Сначала просто раскидываем пропорционально стоимости. Не цене - именно стоимости. Проверяем итоговую сумму - она может различаться на копейки в ту или другую сторону, причём этих копеек гарантированно не больше, чем позиций в заказе. Выводим сумму в нужную, отнимая по копейке от соответствующего количества самых дорогих позиций, либо прибавляя. Затем пересчитываем цену, строго с округлением вверх - если произведение количества на цену окажется больше итоговой суммы, наплевать, это в принципе ненаказуемо.

И, собственно, это всё.

PS. Не расскажете, как у двух позиций с суммами 10000 и 2100 получилась общая сумма без скидки 11050?

Answer 1

[Wataru]

Во-первых, давайте считать в копейках. Умножте все цены на 100 перед началом алгоритма, и поделите на 100 при выводе. Потому что никогда нельзя деньги считать или хранить в вещественных числах. При сериализации и внешних интерфейсах, конечно, придется запятые ставить, но лучше при выводе выводить x/100, "," и x%100. И молиться, что у читателя хватит точности это прочитать, если он, конечно, не заморачивается с подобным трюком.

Далее алгоритм (на псевдокоде):
total_price - изначальная цена. goods[i].price - цена товара, goods[i].amount - количество товара, discount - сколько скидки.

discount_left = discount
for i in 1..n {
  cur_discount = discount * goods[i].price / total_price # целочисленное деление нацело с округлением вниз.
  goods[i].price -= cur_discount
  discount_left -= cur_discount*goods[i].amount
}
for i in 1..n {
  if discount_left == 0: break
  if goods[i].amount <= discount_left {
    goods[i].price -= 1;
    discount_left -= goods[i].amount
  }  else {
   // разбиваем категорию на 2 штуки, в одной discount_left товаров, в другой остальное.
   new_good = Good{.price = goods[i].price-1, .amount = discount_left}
   goods[i].amount -= discount_left
   discount_left = 0
   goods.append(new_good)
   break
  }
}

Как это работает: если бы мы могли идеально делить копейки с любой точностью, то каждый товар получил бы скидку price*discount/total_price. Одинаковый процент скидки везде. но у нас-то целые копейки, поэтому если мы эти скидки округлим вниз, то мы сколько-то копеек недоскинем. Но для каждой штуки товара мы потеряли меньше одной копейки, а значит суммарно - меньше общего количества товаров. Значит можно из каких-то товаров вычесть 1 и все сойдется. Вот и вычитаем из первых discount_left товаров. Если категория целиком покрыта - просто уменьшаем у нее цену. Если нет, то разбиваем на 2 куска и у одного цену уменьшаем.

Тут могут быть проблемы, если скидка очень большая и есть товары очень маленькой стоимости. Скажем, товар стоимостью 5 копеек и кидка в 85% уже между 0 и 1. Округленная вниз она будет 4, но вот если вы из этого товара потом еще и 1 вычтите, то может так получится, что вы снизите цену до 0. Допустимо ли это? Чтобы этого избежать надо товары отсортировать по убыванию цены. Но все равно может не помочь, тогда надо тогда такие товары ценой в 1 копейку исключить из рассмотрения и запустить цикл вычитания 1 опять, если после цикла discount_left не 0.

Второй момент, если вам очень хочется избегать разбиения категорий на части, то можно попробовать реализовать динамическое программирование для решения задачи размена монет, и таким образом найти какие категории надо взять целиком, чтобы набрать discount_left. Но вряд ли вам это так уж надо, ибо предвижу весьма частый случай, когда разбивать все-равно придется. Да и разбиение тут максимум одно происходит.