О среднем числе допустимых решений в задаче о рюкзаке

doi:10.17223/20710410/68/7

Эндаумент фонд ТГУ!
Впиши своё имя в историю университета
- Сделать пожертвование -

Add to "Quick Collection"

Description	Size	Format
О среднем числе допустимых решений в задаче о рюкзаке	287 KB	Adobe Acrobat PDF	Read	Download
DOI Доступ к ресурсу на сайте издателя			10.17223/20710410/68/7

#задача о рюкзаке

#функции производящие

#динамическое программирование

#NP-полные задачи

#метод коэффициентов

Title: О среднем числе допустимых решений в задаче о рюкзаке
Title: On the average number of solutions in the knapsack problem
Creator: Волков, Мария Сабина Александровна
|
Гордеев, Эдуард Николаевич
|
Леонтьев, Владимир Константинович
Date: 2025
DOI: 10.17223/20710410/68/7
Description: Анализируются характеристики решений задачи об ограниченном рюкзаке. Выведены выражения для вычисления среднего значения целевой функции среди всех допустимых решений, а также формулы, связывающие количество решений с подзадачами меньшей размерности. Для случаев, когда переменные принимают значения из множества {0,1} или {0,1, 2}, определены формулы для оценки среднего числа допустимых решений во всех задачах заданной размерности при ограниченных значениях коэффициентов весов. Рассмотрена производящая функция, описывающая количество решений рюкзачных задач фиксированной размерности, где компоненты вектора весов принадлежат заданному диапазону. Полученные результаты могут быть полезны при анализе вычислительной сложности алгоритмов решения задачи о рюкзаке.