Как найти возможные суммы из N элементов в массиве

Доброго всем дня, меня вдохновила статья «Всё, что вы хотели знать о динамическом программировании, но боялись спросить», за что Вам огромное спасибо.

Приоритет нашей задачи: минимизация времени выполнения поиска, так как полная проверка уходит в арифметическую прогрессию.

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