Подробное описание документа

Волков М. С. А., Гордеев Э. Н., Леонтьев В. К.
   О свойствах решений обобщенной задачи о рюкзаке / Волков М. С. А., Гордеев Э. Н., Леонтьев В. К. // Безопасные информационные технологии (БИТ – 2023) : материалы 12-ой Международной научно-технической конференции, посвященнойя 25-летию кафедры ИУ8, Москва, 1-2 ноября 2023 года / МГТУ им. Н. Э. Баумана (национальный исследовательский университет). - М., 2024. - С. 10-15.

Рассмотрены комбинаторные свойства множества решений в задачах об ограничен-ном рюкзаке. Найдены производящие функции для множества допустимых решений задачи и для значений функционала задачи на этом множестве. Получены формулы, позволяющие вычислять среднее значение оптимизируемой функции на множестве допустимых решений задачи о рюкзаке и выражать мощность этого множества через число решений подзадач меньшей размерности. Для случаев булевых переменных и переменных из множества {0, 1, 2} получены формулы для расчета среднего числа допустимых решений на множестве всех задач заданной размерности с коэффициентами, не превышающими заданной величины. Найденные выражения могут быть использованы в качестве вспомогательных процедур в алгоритмах решения задач.
Ключевые слова: задача о рюкзаке, производящие функции, методы декомпозиции, NP-полные задачи, метод коэффициентов