Доброго всем дня, меня вдохновила статья "Всё, что вы хотели знать о динамическом программировании, но боялись спросить", за что Вам огромное спасибо.
Приоритет нашей задачи: минимизация времени выполнения поиска, так как полная проверка уходит в арифметическую прогрессию.
Где я использую этот модуль? Мне была поставлена задача распределения разносортного товара на паллеты, "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") Тогда //////////////////////////// пока не перебор, записывать НоваяСтрока = НовыйДокумент.Продукция.Добавить(); ЗаполнитьЗначенияСвойств(НоваяСтрока, СтрокаТЗ); НоваяСтрока.НомерПалета = НомерПалета; //////////////////////////// Иначе Прервать; КонецЕсли; КонецЦикла; НовыйДокумент.Записать(РежимЗаписиДокумента.Проведение);
