Какой оптимальный алгоритм для однозначного определения слагаемых в сумме?
У бизнеса такая проблема. Почтой отправляются заказы клиентов наложенным платежом (это когда оплата при получении), они в обработке (отправка, получение, обработка платежа) находятся пару недель. В текущей ситуации у нас может быть единовременно 20-50 заказов в разном статусе отправки.
После оплаты заказов раз в несколько дней мы получаем от почты платеж. Единой суммой. И нам важно знать конкретные заказы, которые были оплачены. Этой информации в платежке нет.
Появилась идея регулировать это при помощи сумм заказа. Мы готовы идти на определенные издержи, предоставляя небольшую скиду, чтобы потом по сумме понимать, какие заказы были оплачены.
Из студенческих времен помню, что есть какие-то математические теории, которые помогут зашифровать таким образом данные. чтобы потом по сумме можно было их однозначно расшифровать.
Что должен уметь алгоритм.
1) Допустим, у нас есть уже отправленные, но еще не закрытые сделки с суммами S1, S2, S3..., Sn. Нам поступает заказ с суммой заказ Z0. Нам нужно поменять его цену таким образом, чтобы итоговая его цена была Z1 такая, что не существует такого набора индексов i, j, ..., k, и a, b, ..., c , что Si + Sj + ... + Sk = Z1 + Sa + Sb + ... + Sc, при этом из всех возможных вариантов Z1 должны быть выбрана такая, чтобы разница |Z0-Z1| была минимальна.
2) Нам поступает платеж от Почты с суммой P. Алгоритм должен однозначно определить i, j, .. , k, такие, что Si + Sj + Sk = P
А с математической точки зрения, если у вас в пути 50 товаров, то есть 2**50 вариантов суммы в платёжке. Что бы отправить новый товар вам нужно подобрать его цену так что бы он в сумме с любым из этих вариантов не совпал ни с каким другим. С точки зрения математики это несложно, а с практической точки зрения перебирать триллионы вариантов нереально.
С математической точки зрения вы налетаете на нехилые бабки. Например, если есть заказы на сумму 1, 2, 4, ... , 2^N, то минимальная сумма, удовлетворяющая указанным требованиям - это 2^(N+1).
После оплаты заказов раз в несколько дней мы получаем от почты платеж. Единой суммой. И нам важно знать конкретные заказы, которые были оплачены. Этой информации в платежке нет.
Любое перечисление должно сопровождаться детализирующим документом, который позволяет точно идентифицировать каждую копейку. Вам ОБЯЗАНЫ предоставлять эту информацию.
Просто представь, что есть заказы с разным НДС (для справки - например, программное обеспечение НДС не облагается). Налоговая-то разбираться не будет, слупит его со всей суммы. А потом ещё и штрафом нехилым отполирует.
Если представить стоимость отдельного заказа (в копейках) в 2-ричной системе счисления (набор бит) и каждый заказ должен устанавливать только свой бит (брать младшие биты, установив остальные в 0), то сумма этих чисел в младших разрядах будет аналогично битовой операции OR, т.е. по итоговой сумме можно будет однозначно понять, какой заказ был включен в нее.
После получения платежки мы получим в сумме в младших битах те заказы - что оплачены, и для последующих заказов берем эти освободившиеся битовые позиции.
Пример, берем младшие 4 бита для адреса (возможность одновременно быть в обработке 4-ем заказам)
1 - 10110001 цена 177р
2 - 01100010 цена 98р
3 - 11110100 цена 244р
4 - 00011000 цена 24р
если платежка пришла по 3-ем заказам, например 1+2+4 то это даст сумму 299р - 100101011, смотрим на младшие биты, установлены 1,2 и 4
Недостаток, 20 заказов это 2^20 копеек - это разница в цене на 10т.р. (т.е. 20-ый заказ может отличаться по цене от первоначального на эту сумму), так же это накладывает ограничение на минимальную цену заказа (можно подбирать для дешевых заказов младшие биты а для по дороже - по старше.
Логично что это подойдет только если заказов мало, например 2^10 это всего 10.24р
К сожалению если не добавить какого то еще знания о возможностях группировки заказов, то это никак не оптимизировать
Самое простое - шифруйте последние 2 цифры номера заказа как копейки в сумме платежа. Или 3 цифры - как последняя цифра рублевой суммы + копейки. Уникальности не будет, но сократить количество кандидатов в 100-1000 раз может оказаться вполне достаточно для вашей задачи.
Но это такое себе решение. Вообще у наложенного платежа (а бланк наложенного платежа, по идее, готовите вы как отправляющая сторона) есть поле "назначение". И почта обязана вам его отдавать вместе с платежом. Что мешает вписать в назначение номер заказа в вашей системе? "Оплата заказа #XXX-YYY-ZZZZ" или как-то так.
Тут предлагают биты устанавливать, это рабочее решение, но погрешность большую вносит. Часто можно гораздо лучше сделать. Вам надо добиться того, чтобы никакую сумму нельзя составить разными подмножествами активных заказов, так ведь?
Сначала полным перебором найдите суммы всех подмножеств. Если есть совпадения, возьмите минимальную сумму, которую можно набрать больше 1 раза. Вычтите из случайного заказа 1 копейку. Повторяйте процесс. Если цены правдоподобны, сильно больше 100 копеек и цены различаются, то даже для 20 заказов вам придется лишь несколько копеек вычесть.
Правда, если куча заказов с одинаковой ценой, то тут придется также младшие биты менять.
Простой
Средний
Сложный
