Оптимизация подбора кусков заданного суммарного метража методом ветвей и границ

FastCode 63 8

Имеется таблица "Метраж", содержащая информацию о количестве кусков и их метраже: индекс куска, количество кусков, размер куска, общий метраж индекса. Требуется при вводе заданного метража подобрать куски, оптимально составляющие заданный метраж. Желательно использовать минимум кусков вообще и минимум разных кусков. Задача решается методом ветвей и границ. Этот метод заключается в сокращенном переборе вариантов. Сокращение достигается за счет предварительной оценки развиваемого варианта. Если оценка хуже уже полученного рекорда, развитие прекращается. В первую очередь развиваются самые перспективные варианты. Решение представляет собой две функции. В первой производится подготовка, а во второй рекурсивной функции - собственно решение:

Автор: ildarovich

Процедура КнопкаСформироватьНажатие(Кнопка) 
    РабочаяТаблица = Метраж.Выгрузить(); 
    РабочаяТаблица.ЗаполнитьЗначения(Метраж.Итог("Имеется"), "НужноВзять"); 
    Метраж.ЗагрузитьКолонку(РабочаяТаблица.ВыгрузитьКолонку("НужноВзять"), "НужноВзять"); 
    РабочаяТаблица.ЗаполнитьЗначения(0, "НужноВзять"); 
    РабочаяТаблица.Сортировать("Коэффициент Убыв"); 
    ПодборКусков(РабочаяТаблица, РабочаяТаблица.Количество() - 1, Требуется) 
КонецПроцедуры

Процедура ПодборКусков(РабочаяТаблица, ВГраница, ЗаданнаяСумма, УжеВзяли = 0) Экспорт  
    Если ВГраница < 0 ИЛИ ЗаданнаяСумма < 0 ИЛИ УжеВзяли >= Метраж.Итог("НужноВзять") Тогда //промах  
        Возврат      
    ИначеЕсли ЗаданнаяСумма = 0 Тогда //фиксируем решение  
        Ответ = РабочаяТаблица.Скопировать( , "НомерСтроки, НужноВзять"); 
        Ответ.Сортировать("НомерСтроки"); 
        Метраж.ЗагрузитьКолонку(Ответ.ВыгрузитьКолонку("НужноВзять"), "НужноВзять")  
    КонецЕсли;  
    Курсор = РабочаяТаблица[ВГраница];  
    Для НужноВзять = 0 По Курсор.Имеется Цикл  
        Курсор.НужноВзять = НужноВзять;  
        ПодборКусков(РабочаяТаблица, ВГраница - 1, ЗаданнаяСумма - НужноВзять * Курсор.Коэффициент, УжеВзяли + НужноВзять);          
        Курсор.НужноВзять = 0 
    КонецЦикла 
КонецПроцедуры // ПодборКусков() 
OneTracker - трекер учета рабочего времени программиста 1С

Похожие публикации

Установка границы

Задать вопрос

Создать временную таблицу периодов с заданной периодичностью

Посчитать запросом суммарную длительность различных состояний

Обработка подбора в управляемой форме

Модератору