48282

Автор(ы): 

Автор(ов): 

3

Параметры публикации

Тип публикации: 

Статья в журнале/сборнике

Название: 

Метод таблиц допустимых решений в задаче о ранце

DOI: 

10.14529/ctcr180204

Наименование источника: 

  • Вестник Южно-Уральского государственного университета. Серия: Компьютерные технологии, управление, радиоэлектроника

Обозначение и номер тома: 

Т. 18, № 2

Город: 

  • Челябинск

Издательство: 

  • Издательский центр ЮУрГУ

Год издания: 

2018

Страницы: 

38-53
Аннотация
Предложен новый подход к получению верхних и нижних оценок для задачи о ранце, в основе которого лежат операции «склеивания» решений одного слоя (k-слоем называется множество решений, у которых определены первые k компонент, соответствующих предметам). Рассмотрены две операции склеивания. При первой операции склеивания не теряется ни одно из допустимых решений, но могут появиться недопустимые. При этом мы получаем верхнюю оценку решений задачи. Во второй операции остаются только допустимые решения, но не все. При этом мы получаем нижнюю оценку решений задачи. В статье представлены результаты численных экспериментов по оценке времени и точности предлагаемого подхода в зависимости от объёма входных данных, объёма рюкзака и величины склеивания.

Библиографическая ссылка: 

Бурков В.Н., Корепанов В.О., Кашенков А.Р. Метод таблиц допустимых решений в задаче о ранце // Вестник Южно-Уральского государственного университета. Серия: Компьютерные технологии, управление, радиоэлектроника. 2018. Т. 18, № 2. С. 38-53.