Производящие функции в задаче о ранце

 
Код статьиS086956520002139-5-1
DOI10.31857/S086956520002139-5
Тип публикации Статья
Статус публикации Опубликовано
Авторы
Аффилиация: Вычислительный центр Российской Академии наук Федерального исследовательского центра “Информатика и управление”
Аффилиация: Московский государственный технический университет
Название журналаДоклады Академии наук
ВыпускТом 481 Номер 5
Страницы478-480
Аннотация

Рассматривается задача о ранце с булевыми переменными и одним ограничением. Получены комбинаторные формулы, позволяющие вычислять и оценивать мощность множества допустимых решений и значения функционала в различных случаях в зависимости от набора заданных параметров задачи. В качестве параметров берутся коэффициенты целевой функции, вектора ограничений и объём рюкзака. Базовой техникой является классический метод производящих функций. Результаты, полученные в работе, могут быть использованы для оценки трудоёмкости переборных и декомпозиционных методов решения задачи, а также непосредственно при их разработке в качестве вспомогательных процедур.

Ключевые слова
Получено30.10.2018
Дата публикации30.10.2018
Цитировать   Скачать pdf Для скачивания PDF необходимо авторизоваться
Размещенный ниже текст является ознакомительной версией и может не соответствовать печатной.

всего просмотров: 1253

Оценка читателей: голосов 0

1. Леонтьев В. К. Производящие функции в задаче о ранце. В сб.: Материалы XI Международного семинара “Дискретная математика и ее приложения”. М.: МГУ, 2012. С. 415–416.

2. Леонтьев В. К. Комбинаторика и информация. Ч. 1. Комбинаторный анализ. М.: МФТИ, 2015. 174 с.

3. Егорычев Г. П. Интегральное представление и вычисление комбинаторных сумм. Новосибирск: Наука, 1977.

4. Kellerer H., Pferschy U., Pisinger D. Knapsack Problems. B.: Springer, 2004.

5. Дюбин Г. Н., Корбут А. А. Поведение в среднем жадных алгоритмов для минимизационной задачи о ранце — общие распределения коэффициентов // ЖВМиМФ. 2008. Т. 48. № 9. С. 1556–1570.

Система Orphus

Загрузка...
Вверх