Решение задачи о наполняемости ранца с помощью запросов.

Немного предыстории. Организация периодически проводит маркетинговую акцию в розничной торговле. На какую сумму товара пробито в чеке, на столько же можно выбрать еще «подарков». По факту часть товара в чеке ставится со 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ИзТаблицыПоНомеру(Выборка.А);
КонецЕсли;