gifts2017

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

Опубликовал Сергей Колган (serg17) в раздел Программирование - Практика программирования

Представляю Вашему вниманию алгоритм перебора вариантов «наполняемости ранца» с помощью запросов. При определенных условиях он работает быстрее чем обычный рекурсивный перебор.

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

 

 

См. также

Подписаться Добавить вознаграждение

Комментарии

1. Анатолий Бычин (tolyan_ekb) 26.04.13 05:44
Кому полезна данная статья? В ней даже примера кода нет для дальнейшего использованиея )) В чем преимущества/недостатки перед описаными алгоритмами в вики?
2. Алексей Гафуров (Alex_grem) 26.04.13 09:25
3. Сергей Колган (serg17) 26.04.13 09:34
В статье описывается не какой то "новый" алгоритм. Это полный перебор в чистом виде. Просто немного необычная программная реализация. Я пробовал его реализовать таким образом у одного клиента. Но, как я уже писал, там была необходимость работы в файловом режиме. Поэтому "не пригодилось". И поэтому я не проводил полномасштабных исследований с замерами производительности.
По поводу отсутствия примера кода - согласен, это недостаток. Просто примера уже реализованного кода не сохранилось. А написать снова - банальная нехватка времени. Может быть добавлю чуть позже.
На данный момент просьба рассматривать статью как некую "абстрактную" идею :)
4. Сергей (ildarovich) 26.04.13 11:11
Просьба пояснить исходную задачу: чем определяется число N? - Это число позиций в чеке? - Число позиций в магазине? - Задача решается "за покупателя"? - Какова была идея рекурсивного алгоритма? - Использовался ли там метод ветвей и границ?
5. Сергей Колган (serg17) 26.04.13 12:19
Пожалуй задача в чистом виде отличается от классической задачи о наполнении ранца.
Число N - суммарное количество позиций в документе.
Т.е. изначально весь товар разбивался на строки с количеством = 1. Но с произвольной суммой.
Далее определялось, на какие строки ставить скидку 100%.

Да, задача решается "за покупателя".
Рекурсивный алгоритм был написан еще до меня.
Насколько я помню, это был алгоритм полного перебора, по следующему принципу:

На текущую строку ставится ли скидка 100% Да | Нет - считается общая сумма.
Соответственно вызов рекурсии для следующей строки для каждого из 2 вариантов.
Если накопленная сумма превысила некое пороговое значение, значит далее рекурсия не идет.
Также было ограничение, если по какому то варианту сумма стала РАВНА пороговому значению, перебор заканчивался.

Решайте сами, можно ли данный способ отнести к методу ветвей и границ.
6. Сергей (ildarovich) 26.04.13 12:52
(5) Мне непонятен экономический смысл данной задачи. Что я пока понял: покупатель взял в торговом зале N нужных ему товаров. Каждый в количестве 1, причем могут быть одинаковые. У каждого товара есть фиксированная цена. По условиям акции он может заплатить примерно половину их суммарной стоимости по ценнику. Считается общая стоимость, а затем товар делится на две как можно более равные по стоимости группы. За одну группу в чеке указывается полная стоимость, вторая показывается как бесплатная - со скидкой 100%.
А в чем смысл всего этого? Зачем это делать? - Не проще ли дать скидку 50% на весь товар? Подтолкнуть покупателя брать всего по два? - Тогда скидка будет максимальной. Странно решать оптимизационную задачу (перебирать миллиард вариантов) после того как покупатель уже выбрал товар и ничего не может изменить. Нет обратной связи. Бессмысленная задача. Математически интересная, но бессмысленная. Не стоило заниматься. Или я не прав? Думаю проблема в том, что заказчик где-то слышал про подобную акцию, но неправильно понял как она правильно проводится.
7. Сергей Колган (serg17) 26.04.13 13:27
Это если рассматривать задачу с технической точки зрения.
А для покупателя условия акции звучали примерно так:
Если вы покупаете товара БОЛЬШЕ чем на 10 000, то вы можете выбрать подарков ЕЩЕ на столько же.
Но не более половины чека.
Т.е. если купили на 9000 - подарков нет.
Если на 11000 - могут набрать еще подарков на 11000. Т.е чек без скидок 22000, но платят покупатели 11000.
8. Сергей (ildarovich) 26.04.13 14:08
(7) Теперь понятнее. Но все же кажется логичным отдать расчеты покупателю: он раскладывает покупки на две кучки: это больше 10000 для получения подарков, а это - не более суммы первой "кучки" - сами подарки. Так что остаюсь пока при своем мнении: эта задача - ошибка заказчика. А жаль - очень интересуют оптимизационные задачи применительно к 1С.
По сути Вашего решения могу сказать, что таблица вариантов необходима всего одна. В ней должны быть строки "00000...01", "00000...10". Эти строки должны быть отсортированы по числу единиц. В запросе должно быть Выбрать первые 1. Сортировка - долгая операция, поэтому, хотя таблицу легко динамически построить методом Порождающего запроса, ее действительно лучше предпостроить и хранить. Условие соединения таблиц можно записать по примеру из статьи "Выразить строку как число и строку как дату в запросе", только вместо веса позиции будет цена товара. Файловая версия и SQL не должны сильно различаться по скорости решения - здесь в любом случае идет сканирование индекса.
Но этот подход, хотя и улучит Ваше решение, будет работать только до примерно 20-ти позиций (как и рекурсия). Так что нужны другие подходы.
9. al petrov (petrov_al) 26.04.13 17:31
Опять математические изыскания...господа пожалуйста будьте ближе к реалиям нашей жизни. Хотя вроде интересно, но блин нет времени этим заниматься работы валом.
10. Сергей Колган (serg17) 26.04.13 18:51
(8) ildarovich,
Как раз покупателю отдавать расчеты не вариант. Придет большой лысый дядечка. Наберет товара на 30000. Об акции узнает только на кассе обрадуется. И спросит "Так сколько с меня денег". Или другой случай. Покупатель (или продавец) как то посчитал. А потом придя домой и внимательно глядя на чек увидел другой вариант раскидывания "подарков", при котором он бы заплатил меньше денег. Нет рассчитывать надо по возможности на автомате, причем наилучшим способом. Поэтому задача и имеет вполне прикладную часть(to 9).
На самом деле при N больше 14 время на расчет уходило "непозволительно" много. Больше минуты точно. А при большой очереди это не вариант. В таком случае расчет "перекладывался" на продавца. С учетом того, что стоимость одной номенклатурной позиции была от 1500 - вполне всех все устраивало.
Сортировка по числу единиц - очень хорошая идея. Согласен.
На счет файловой версии и SQL... На 100% утверждать не могу т.к. не проверял. Но что то мне не верится что файловая СУБД соединяет таблицы в многие миллионы записей с той же скоростью что и SQL.
Соединения таблиц по приведенному примеру с ходу не понял, а долго разбираться как то лень если честно.
11. Петр Астахов (Zebar) 30.04.13 15:49
Собственно, а почему бы не просто предоставить скидку 50% на все товары?
12. Сергей Колган (serg17) 30.04.13 20:22
Потому что условия акции оговорены так:
"Если вы покупаете товара БОЛЬШЕ чем на 10 000, то вы можете выбрать подарков ЕЩЕ на столько же."
Этот же текст в массовой СМС рассылке покупателям.
Такой маркетинговый ход. И требование было именно выделять в чеке подарки путем 100%ной скидки.
На самом деле здесь игра на психологии покупателя.
И т.к. подобные акции проводятся не первый год - думаю результатом они довольны.
13. Two World (Prometeus2011) 12.08.15 17:40
(6) ildarovich, Смысл скрывается в контроле прибыли по итогам закрытия квартала. Например, есть организация, которая продает мелочь всякую (в России еще качают, правда, но эта отдельная организация - продает). Вот в конце квартала надо этой организации показать определенную прибыль на счете 90.9. Причем, прибыль должна быть заданной величины........... В общем, для этого и применяется заполнение документов.... причем номенклатурное соответствие документов бух. учета и оперативного учета, как это сказать по-мягче... не является условием ТЗ Даже наоборот.
Для написания сообщения необходимо авторизоваться
Прикрепить файл
Дополнительные параметры ответа