Немного предыстории. Организация периодически проводит маркетинговую акцию в розничной торговле. На какую сумму товара пробито в чеке, на столько же можно выбрать еще «подарков». По факту часть товара в чеке ставится со 100% скидкой. И эта часть товара должна быть максимально приближена к половине общей суммы (без скидок), но не превышать ее.
Т.о. приходится решать задачу о наполняемости рюкзака, причем за максимально короткое время. Существующий алгоритм перебора с помощью рекурсии был оптимизирован более чем. Я решил попробовать принципиально другой подход.
Сначала объясню в теории. Весь товар разбивается по количеству на несколько строк. То есть в каждой строке «Количество = 1». В итоге есть массив сумм построчно X1…Xn. Для тех, кто знаком с комбинаторикой понятно, что количество вариантов для перебора равно 2 в степени N.
Формируем таблицу (матрицу) размерности N столбцов, 2 в степени N строк, состоящую из 0 и 1, которая по сути представляет все возможные варианты.
00..00
00..01
…….
11..01
11..11
Далее производим «перемножение» массива X1…Xn и данной матрицы по алгебраическим правилам. В итоге получаем массив Y(1)…Y(2 в степени N) результатов, из которых просто необходимо выбрать наиболее подходящий вариант. Тот, который наиболее близок к некому пороговому значению P, но не превышает его.
Теперь собственно как это реализовать с помощью запросов. Таблицу из 0 и 1 я несколько модифицировал. В итоге получил таблицу из 3 столбцов и N*(2 в степени N) строк, вида
Ai | Bj | (0 или 1)
Где Ai – номер строки в исходной таблице, Bj – номер столбца в исходной таблице, (0 или 1) – соответствующее значение.Все таблицы с N = 2 по (некое приемлемое значение, при котором расчет не зависает окончательно) я буферизовал в базе. Т.о. время на их составление не тратится. Эти таблицы передаются как параметр в запрос.
Массив X1…Xn представляем в виде таблицы из 2 колонок:
1 | X1
2 | X2
…
N | Xn
И тоже передаем в запрос. В запросе происходит соединение по равенству Bj (для первой таблицы) и первой колонки второй таблицы. В итоге получаем таблицу из 4 колонок вида:
Ai | Bj | (0 или 1) | Xj
Перемножаем 3 и 4 колонку. Получаем таблицу вида:
Ai | Bj | (0 или Xj)
Далее группируем по Ai, суммируя по третьей колонке. Получаем:
Ai | ∑ (0 или Xj) То есть таблицу из двух колонок вида Ai | Ci.
Далее элементарно отбор по условию Ci
На выходе получаем Ai – это номер строки в нашей исходной таблице 0 и 1, который соответствует нужному варианту.
Теперь собственно о плохом. Как показали замеры производительности, на файловой базе подобный способ безбожно проигрывает рекурсивному перебору вех вариантов. Поэтому он так и не использовался. На SQL проявляет себя очень неплохо.
Ну и основная проблема – большие значения N. Я не проверял, как будет отрабатывать на больших числах, т.к. такой необходимости не было. Но что-то мне подсказывает, что для N больше 30, например, таблицу в миллиард записей SQL если и обработает, то за не очень приемлемое время.
p.s. По просьбе трудящихся выкладываю пример запроса.
Каждый шаг вынес в отдельный запрос пакета, чтобы было понятнее.
ТЗ1 = ПолучитьТаблицу0и1РазмерностиN(Н); //Таблица из 3 колонок вида Ai | Bj | (0 или 1)
ТЗ2 = ПолучитьТаблицуДляМассиваЗначений(); //Таблица из 2 колонок вида i | Xi
Запрос = Новый Запрос;
Запрос.Текст = "ВЫБРАТЬ
| Тз1.А,
| Тз1.В,
| Тз1.Х
|ПОМЕСТИТЬ Тз1
|ИЗ
| &Тз1 КАК Тз1
|;
|
|////////////////////////////////////////////////////////////////////////////////
|ВЫБРАТЬ
| Тз2.Н,
| Тз2.ХН
|ПОМЕСТИТЬ Тз2
|ИЗ
| &Тз2 КАК Тз2
|;
|
|////////////////////////////////////////////////////////////////////////////////
|ВЫБРАТЬ
| Тз1.А,
| Тз1.В,
| Тз1.Х * Тз2.ХН КАК Х
|ПОМЕСТИТЬ НеСгруппированно
|ИЗ
| Тз1 КАК Тз1
| ВНУТРЕННЕЕ СОЕДИНЕНИЕ Тз2 КАК Тз2
| ПО Тз1.В = Тз2.Н
|;
|
|////////////////////////////////////////////////////////////////////////////////
|ВЫБРАТЬ
| НеСгрупированно.А,
| СУММА(НеСгрупированно.Х) КАК Х
|ПОМЕСТИТЬ Сгруппировано
|ИЗ
| НеСгруппированно КАК НеСгрупированно
|
|СГРУППИРОВАТЬ ПО
| НеСгрупированно.А
|;
|
|////////////////////////////////////////////////////////////////////////////////
|ВЫБРАТЬ ПЕРВЫЕ 1
| Сгруппировано.А
|ИЗ
| Сгруппировано КАК Сгруппировано
|ГДЕ
| Сгруппировано.Х |
|УПОРЯДОЧИТЬ ПО
| Сгруппировано.Х УБЫВ";
Запрос.УстановитьПараметр("ТЗ1",ТЗ1 );
Запрос.УстановитьПараметр("ТЗ2",ТЗ2 );
Запрос.УстановитьПараметр("Р",НекоеПороговоеЗначение);
Результат = Запрос.Выполнить();
Выборка = Результат.Выбрать();
Если Выборка.Следующий() тогда
ОптимальнаяСтрокаИз0и1 = ПолучитьСтроку0и1ИзТаблицыПоНомеру(Выборка.А);
КонецЕсли;
