Доброго всем дня, меня вдохновила статья "Всё, что вы хотели знать о динамическом программировании, но боялись спросить", за что Вам огромное спасибо.
Приоритет нашей задачи: минимизация времени выполнения поиска, так как полная проверка уходит в арифметическую прогрессию.
Где я использую этот модуль? Мне была поставлена задача распределения разносортного товара на паллеты, "1" это метр кубический - объем помещающийся на паллет. У меня была мысль раскидать по объему товар 0,25 / 0,5 / 0,75 и логически складывать, 0,5 +0,5 / 0,75 + 0,25, но это породило огромное количество когда , чем дальше, тем сложнее это было.
Для моей задачи выходом стала "Ленивая динамика:" из вышеуказанной статьи.
В этом примере из статьи идет последовательное сложение строк и перебор в цикле с какого элемента начинать сложение - перебор вариантов сложения.
Я много раз переписывал и нашел предполагаю оптимальный путь. Остается та же методика последовательного сложения строк, только на каждом этапе ( ступени ) он перед следующим шагом перепроверяет попытку сложения со всеми возможными вариантами, исключая уже использованные в сложении.
Это рабочий код из моей программы, отлаженный.
Таблица000//(Таблица Значений с товаром),
Эдиал = 1; //=1 метру кубическому
КоличествоСтрокТаб = Таблица000.Количество();//количество строк
ОтклонениеВПлюс =Число("0,1");//до 1,1
ОтклонениеВМинус = Число("0,1");//до 0,9
ОптимальнаяРазница = Эдиал;//задаем максимальную разницу
ОптимальнаяСумма = 0;
//задаем 2 табличные части или можно использовать массивы, по вкусу
ОптимальнаяТаблицаСтрок = Новый ТаблицаЗначений;
ОптимальнаяТаблицаСтрок.Колонки.Добавить("НомерСтрокиП");
ТаблицаСтрок = Новый ТаблицаЗначений;
ТаблицаСтрок.Колонки.Добавить("НомерСтрокиП");
/////////////////////////////////////////////////////////////////////////////////
//Цикл от первого элемента к последнему
Для СтартСчетчик = 0 По КоличествоСтрокТаб-1 Цикл
Счетчик = СтартСчетчик;//стартовое смещение
ТаблицаСтрок.Очистить();
ТекущаяСумма = 0;
Для ТекущийСчетчик = 0 По КоличествоСтрокТаб-1 Цикл //переменная нигде
//не используется, это клон первого цикла , контроль количества повторений,
//а первый цикл только задает последовательный обход с кого начинать
Если Счетчик = КоличествоСтрокТаб Тогда //если уходим за таблицу то в начало
Счетчик = 0;
КонецЕсли;
НоваяСтрока = ТаблицаСтрок.Добавить();//постепенно наполняем таблицу
НоваяСтрока.НомерСтрокиП = Счетчик;
ТекущаяСумма = ТекущаяСумма + Таблица000[Счетчик].ОбъемТары;
//объем Количество "/" Количество помещающее на паллет
ВнутреннийСчетчик = Счетчик+1;//временная переменная
Если ВнутреннийСчетчик = КоличествоСтрокТаб Тогда
//если уходим за таблицу то в начало
ВнутреннийСчетчик = 0;
КонецЕсли;
Пока НЕ ВнутреннийСчетчик = СтартСчетчик Цикл
// с каждым углублением количество циклов сокращается
Если ТекущаяСумма > Эдиал + ОтклонениеВПлюс Тогда
//если перебор
Прервать;
КонецЕсли;
ВариантСуммы = ТекущаяСумма + Таблица000[ВнутреннийСчетчик].ОбъемТары;
Если ВариантСуммы >= Эдиал - ОтклонениеВМинус И ВариантСуммы <= Эдиал + ОтклонениеВПлюс Тогда
//если попадает сумма в наш период вычисляем разницу
РазницаСумм = ВариантСуммы - Эдиал;
Если РазницаСумм < 0 тогда //убираем минусы
РазницаСумм = РазницаСумм * -1;
КонецЕсли;
Если РазницаСумм < ОптимальнаяРазница Тогда
ОптимальнаяРазница = РазницаСумм;
ОптимальнаяСумма = ВариантСуммы;
Для Каждого Стр Из ТаблицаСтрок Цикл
//записываем цепочку индексов строк
НоваяСтрока = ОптимальнаяТаблицаСтрок.Добавить();
НоваяСтрока.НомерСтрокиП = Стр.НомерСтрокиП;
КонецЦикла;
//дополняем из временной переменной
НоваяСтрока = ОптимальнаяТаблицаСтрок.Добавить();
НоваяСтрока.НомерСтрокиП = ВнутреннийСчетчик;
Сообщить(Строка(ОптимальнаяСумма));
КонецЕсли;
КонецЕсли;
ВнутреннийСчетчик = ВнутреннийСчетчик +1;
//если уходим за таблицу то в начало
Если ВнутреннийСчетчик = КоличествоСтрокТаб Тогда
ВнутреннийСчетчик = 0;
КонецЕсли;
КонецЦикла;//Пока Цикл
Если ТекущаяСумма > Эдиал + ОтклонениеВПлюс Тогда
Прервать;
КонецЕсли;
Счетчик = Счетчик+1;
КонецЦикла;
/////////////////////////////////////////////////////////////////////////////////////
КонецЦикла;
//добавление колонок и очистка данных
ОднаТаблица = Новый ТаблицаЗначений;
ОднаТаблица = Таблица000.Скопировать();
ОднаТаблица.Очистить();
Для Каждого Стро Из ОптимальнаяТаблицаСтрок Цикл
НоваяСтрока = ОднаТаблица.Добавить();
//заполнение нужных строк
ЗаполнитьЗначенияСвойств(НоваяСтрока, Таблица000[Стро.НомерСтрокиП]);
КонецЦикла;
Расскажу о своей задаче в общем:
В самой стартовой разработке у меня много данных хранилось в переменных, что порождало сбои в программе. Но в 1с есть очень хорошее решение связка Документ - "Регистр остатков" , остается создать документ "прихода", а потом раскидывая товар по паллетам создавая "расход" мы в любую секунду запросом получаем нераспределенный остаток товара, главное только каждый раз очищать документы перед следующим распределением. Будут конкретные вопросы в комментариях, буду рад помочь.
Товары поделены на однотипности, параметры "Фасовка" и "ВидФасовки" за их определение отвечают. В "приходе" не заполняется номер паллета, а вычисляется вышеуказанным методом.
//ОбработкаПроведения(Отказ, Режим)
//Создаем документ с табличной частью, и булево переменной "Приход"
//таким образом мы понимаем что приход, а что расход
Если Приход = Истина Тогда
// регистр РегистрРаспределениеНаПаллеты Приход
Движения.РегистрРаспределениеНаПаллеты.Записывать = Истина;
Для Каждого ТекСтрокаПродукция Из Продукция Цикл
Движение = Движения.РегистрРаспределениеНаПаллеты.Добавить();
Движение.ВидДвижения = ВидДвиженияНакопления.Приход;
Движение.Период = Дата;
Движение.Приход = Приход;
Движение.Вариант = Вариант;
Движение.Номенклатура = ТекСтрокаПродукция.Номенклатура;
Движение.Характеристика = ТекСтрокаПродукция.Характеристика;
Движение.НомерПалета = ТекСтрокаПродукция.НомерПалета;
Движение.Однотипность = ТекСтрокаПродукция.Однотипность;
Движение.Фасовка = ТекСтрокаПродукция.Фасовка;
Движение.ВидФасовки = ТекСтрокаПродукция.ВидФасовки;
Движение.ОбъемТары = ТекСтрокаПродукция.ОбъемТары;
Движение.КоличествоНаОдинПаллет = ТекСтрокаПродукция.КоличествоНаОдинПаллет;
Движение.Количество = ТекСтрокаПродукция.Количество;
Движение.Партия = ТекСтрокаПродукция.Партия;
Движение.ЕдиницаИзмерения = ТекСтрокаПродукция.ЕдиницаИзмерения;
КонецЦикла;
Иначе
// регистр РегистрРаспределениеНаПаллеты Расход
Движения.РегистрРаспределениеНаПаллеты.Записывать = Истина;
Для Каждого ТекСтрокаПродукция Из Продукция Цикл
Движение = Движения.РегистрРаспределениеНаПаллеты.Добавить();
Движение.ВидДвижения = ВидДвиженияНакопления.Расход;
Движение.Период = Дата;
Движение.Приход = Приход;
Движение.Вариант = Вариант;
Движение.Номенклатура = ТекСтрокаПродукция.Номенклатура;
Движение.Характеристика = ТекСтрокаПродукция.Характеристика;
Движение.НомерПалета = ТекСтрокаПродукция.НомерПалета;
Движение.Однотипность = ТекСтрокаПродукция.Однотипность;
Движение.Фасовка = ТекСтрокаПродукция.Фасовка;
Движение.ВидФасовки = ТекСтрокаПродукция.ВидФасовки;
Движение.ОбъемТары = ТекСтрокаПродукция.ОбъемТары;
Движение.КоличествоНаОдинПаллет = ТекСтрокаПродукция.КоличествоНаОдинПаллет;
Движение.Количество = ТекСтрокаПродукция.Количество;
Движение.Партия = ТекСтрокаПродукция.Партия;
Движение.ЕдиницаИзмерения = ТекСтрокаПродукция.ЕдиницаИзмерения;
КонецЦикла;
КонецЕсли;Стартовый обход документа "Приход".
&НаСервере
Функция ФункцияОбходаПрихода() Экспорт
Запрос = Новый Запрос;
Запрос.Текст =
"ВЫБРАТЬ
| РегистрРаспределениеНаПаллеты.Период,
| РегистрРаспределениеНаПаллеты.Регистратор,
| РегистрРаспределениеНаПаллеты.НомерСтроки,
| РегистрРаспределениеНаПаллеты.Активность,
| РегистрРаспределениеНаПаллеты.ВидДвижения,
| РегистрРаспределениеНаПаллеты.Приход,
| РегистрРаспределениеНаПаллеты.Вариант,
| РегистрРаспределениеНаПаллеты.Номенклатура,
| РегистрРаспределениеНаПаллеты.Характеристика,
| РегистрРаспределениеНаПаллеты.НомерПалета,
| РегистрРаспределениеНаПаллеты.Однотипность,
| РегистрРаспределениеНаПаллеты.Фасовка,
| РегистрРаспределениеНаПаллеты.ВидФасовки,
| РегистрРаспределениеНаПаллеты.ОбъемТары,
| РегистрРаспределениеНаПаллеты.КоличествоНаОдинПаллет,
| РегистрРаспределениеНаПаллеты.Партия,
| РегистрРаспределениеНаПаллеты.МоментВремени,
| РегистрРаспределениеНаПаллеты.ЕдиницаИзмерения,
| РегистрРаспределениеНаПаллеты.Количество
|ИЗ
| РегистрНакопления.РегистрРаспределениеНаПаллеты КАК РегистрРаспределениеНаПаллеты
|ГДЕ
| РегистрРаспределениеНаПаллеты.ВидДвижения = ЗНАЧЕНИЕ(ВидДвиженияНакопления.Приход)";
Выборка = Запрос.Выполнить().Выбрать();
//Выборка.Следующий();
Возврат Выборка;
КонецФункции
Функция вычисления следующего паллета для распределения.
&НаСервере
Функция ФункцияМаксимальныйНомерПаллетаПлюсОдин() Экспорт//Следующий
Запрос = Новый Запрос;
Запрос.Текст =
"ВЫБРАТЬ
| МАКСИМУМ(РегистрРаспределениеНаПаллеты.НомерПалета) КАК НомерПалета
|ИЗ
| РегистрНакопления.РегистрРаспределениеНаПаллеты КАК РегистрРаспределениеНаПаллеты";
Выборка = Запрос.Выполнить().Выбрать();
Выборка.Следующий();
Если ЗначениеЗаполнено(Выборка.НомерПалета) Тогда
Возврат Выборка.НомерПалета+1;
Иначе
Возврат 1;
КонецЕсли;
КонецФункции
Далее два запроса на поиск остатков свободного товара, готового к распределению. Параметры "Начало" и "Конец" отвечают за выбираемый объем если требуется. Однотипность - число от 1 и выше.
&НаСервере
Функция ФункцияОстатковСвободныхПоОднотипности(Однотипность, Начало, Конец) Экспорт
Запрос = Новый Запрос;
Запрос.Текст =
"ВЫБРАТЬ
| РегистрРаспределениеНаПаллетыОстатки.Номенклатура,
| РегистрРаспределениеНаПаллетыОстатки.Характеристика,
| РегистрРаспределениеНаПаллетыОстатки.Однотипность КАК Однотипность,
| РегистрРаспределениеНаПаллетыОстатки.Фасовка,
| РегистрРаспределениеНаПаллетыОстатки.ВидФасовки,
| РегистрРаспределениеНаПаллетыОстатки.КоличествоНаОдинПаллет,
| РегистрРаспределениеНаПаллетыОстатки.КоличествоОстаток КАК Количество,
| РегистрРаспределениеНаПаллетыОстатки.КоличествоОстаток / РегистрРаспределениеНаПаллетыОстатки.КоличествоНаОдинПаллет КАК ОбъемТары,
| РегистрРаспределениеНаПаллетыОстатки.ЕдиницаИзмерения,
| РегистрРаспределениеНаПаллетыОстатки.Партия
|ИЗ
| РегистрНакопления.РегистрРаспределениеНаПаллеты.Остатки КАК РегистрРаспределениеНаПаллетыОстатки
|ГДЕ
| РегистрРаспределениеНаПаллетыОстатки.Однотипность = &Однотипность
| И РегистрРаспределениеНаПаллетыОстатки.КоличествоОстаток / РегистрРаспределениеНаПаллетыОстатки.КоличествоНаОдинПаллет <= &Конец
| И РегистрРаспределениеНаПаллетыОстатки.КоличествоОстаток / РегистрРаспределениеНаПаллетыОстатки.КоличествоНаОдинПаллет > &Начало
|
|УПОРЯДОЧИТЬ ПО
| ОбъемТары УБЫВ";
Запрос.УстановитьПараметр("Однотипность", Однотипность);
Запрос.УстановитьПараметр("Начало", Начало);
Запрос.УстановитьПараметр("Конец", Конец);
Результат = Запрос.Выполнить();
Возврат Результат;
КонецФункции
// по всем остаткам
&НаСервере
Функция ФункцияОстатковСвободных(Начало, Конец) Экспорт
Запрос = Новый Запрос;
Запрос.Текст =
"ВЫБРАТЬ
| РегистрРаспределениеНаПаллетыОстатки.Номенклатура,
| РегистрРаспределениеНаПаллетыОстатки.Характеристика,
| РегистрРаспределениеНаПаллетыОстатки.Однотипность КАК Однотипность,
| РегистрРаспределениеНаПаллетыОстатки.Фасовка,
| РегистрРаспределениеНаПаллетыОстатки.ВидФасовки,
| РегистрРаспределениеНаПаллетыОстатки.КоличествоНаОдинПаллет,
| РегистрРаспределениеНаПаллетыОстатки.КоличествоОстаток КАК Количество,
| РегистрРаспределениеНаПаллетыОстатки.КоличествоОстаток / РегистрРаспределениеНаПаллетыОстатки.КоличествоНаОдинПаллет КАК ОбъемТары,
| РегистрРаспределениеНаПаллетыОстатки.ЕдиницаИзмерения,
| РегистрРаспределениеНаПаллетыОстатки.Партия
|ИЗ
| РегистрНакопления.РегистрРаспределениеНаПаллеты.Остатки КАК РегистрРаспределениеНаПаллетыОстатки
|ГДЕ
| РегистрРаспределениеНаПаллетыОстатки.КоличествоОстаток / РегистрРаспределениеНаПаллетыОстатки.КоличествоНаОдинПаллет <= &Конец
| И РегистрРаспределениеНаПаллетыОстатки.КоличествоОстаток / РегистрРаспределениеНаПаллетыОстатки.КоличествоНаОдинПаллет > &Начало
|
|УПОРЯДОЧИТЬ ПО
| ОбъемТары УБЫВ";
Запрос.УстановитьПараметр("Начало", Начало);
Запрос.УстановитьПараметр("Конец", Конец);
Результат = Запрос.Выполнить();
Возврат Результат;
КонецФункции
Функция записи документа.
НомерПалета = ФункцияМаксимальныйНомерПаллетаПлюсОдин();//вышеуказанная
ПеременнаяОбъема = 0;
//цикл по полученной таблице
Для каждого СтрокаТЗ Из ОднаТаблица Цикл
ПеременнаяОбъема = ПеременнаяОбъема + СтрокаТЗ.ОбъемТары;
Если ПеременнаяОбъема <= Число("1,05") Тогда
//////////////////////////// пока не перебор, записывать
НоваяСтрока = НовыйДокумент.Продукция.Добавить();
ЗаполнитьЗначенияСвойств(НоваяСтрока, СтрокаТЗ);
НоваяСтрока.НомерПалета = НомерПалета;
////////////////////////////
Иначе
Прервать;
КонецЕсли;
КонецЦикла;
НовыйДокумент.Записать(РежимЗаписиДокумента.Проведение);
