Анализируются характеристики решений задачи об ограниченном рюкзаке. Выведены выражения для вычисления среднего значения целевой функции среди всех допустимых решений, а также формулы, связывающие количество решений с подзадачами меньшей размерности. Для случаев, когда переменные принимают значения из множества {0,1} ИЛИ {0,1, 2}, определены формулы для оценки среднего числа допустимых решений во всех задачах заданной размерности при ограниченных значениях коэффициентов весов. Рассмотрена производящая функция, описывающая количество решений рюкзачных задач фиксированной размерности, где компоненты вектора весов принадлежат заданному диапазону. Полученные результаты могут быть полезны при анализе вычислительной сложности алгоритмов решения задачи о рюкзаке.
Скачать электронную версию публикации
Загружен, раз: 9
- Title О среднем числе допустимых решений в задаче о рюкзаке
- Headline О среднем числе допустимых решений в задаче о рюкзаке
- Publesher
Tomsk State University - Issue Прикладная дискретная математика 68
- Date:
- DOI 10.17223/20710410/68/7
Ключевые слова
задача о рюкзаке, производящие функции, динамическое программирование, NP-полные задачи, метод коэффициентовАвторы
Ссылки
Kellerer Н., Pferschy U., and Pisinger D. Knapsack Problems. Berlin: Springer, 2004. 548 p.
Martdlo S. and Toth P. Knapsack Problems: Algorithms and Computer Implementations. N.Y.: John Wiley & Sons, 1990. 308 p.
Колпаков P. M., Посыпкин M. А. Верхняя и нижняя оценки трудоемкости метода ветвей и границ для задачи о ранце // Дискретная математика. 2010. Т. 22. Вып. 1. С. 58-73.
Колпаков Р. М., Посыпкин М. А., Си Ту Таит Сип. Верхняя оценка сложности одного из вариантов метода ветвей и границ для задачи о сумме подмножеств // Intern. J. Open Inform. Technol. 2016. V.4. No. 2. P. 1-6.
Колпаков P. M., Посыпкин M. А., Сигал П. X. О нижней оценке вычислительной сложности одной параллельной реализации метода ветвей и границ // Автоматика и телемеханика. 2010. АЛО. С. 156-166.
Колпаков Р. М., Посыпкин М. А. О масштабируемости и эффективности одного метода решения задачи о ранце в распределенной вычислительной среде // Труды ИСА РАН. 2009. Т. 46. С. 164-174.
Колпаков Р. М., Посыпкин М. А. Об эффективной стратегии распараллеливания при решении задач о сумме подмножеств методом ветвей и границ // Дискретная математика. 2019. Т. 31. №4. С. 20-37.
Колпаков Р. М., Посыпкин М. А., Си Ту Таит, Сии. Сложности решения задачи о сумме подмножеств методом ветвей и границ с доминированием и мощностным отсевом // Автоматика и телемеханика. 2017. №3. С. 96-110.
Колпаков Р. М., Посыпкин М. А. Асимптотическая оценка сложности метода ветвей и границ с ветвлением по дробной переменной для задачи о ранце // Дискретн. анализ исслед. опер. 2008. Т. 15. №1. С. 58-81.
Колпаков Р. М., Посыпкин М. А. О наилучшем выборе переменной ветвления в задаче о сумме подмножеств // Дискретная математика. 2017. Т. 29. №1. С. 51-58.
Колпаков Р. М. Оптималвная стратегия решения частного случая задачи о ранце методом ветвей и границ // Вестник Московского университета. Сер. 1. Математика. Механика. 2021. №3. С. 13-22.
Егорычев Г. П. Интегральное представление и вычисление комбинаторных сумм. Новосибирск: Наука, 1977. 285 с.
Леонтьев В. К., Гордеев Э. Н. Производящие функции в задаче о ранце // Доклады АН. 2018. Т. 481. №5. С. 478-480.
Гордеев Э.Н., Леонтьев В. К. О некоторых комбинаторных свойствах задачи о рюкзаке // Ж. вычисл. матем. и матем. физ. 2019. Т. 59. №8. С. 1439-1447.
Леонтьев В. К., Гордеев Э. Н. О числе решений системы булевых уравнений // Автоматика и телемеханика. 2021. №9. С. 150-168.
Волков М. С. А. Комбинаторные свойства задачи об ограниченном рюкзаке // Прикладная дискретная математика. 2024. №63. С. 117-130.
Леонтьев В. К., Гордеев Э. Н. Зависимости среднего числа решений в задаче о ранце от параметров области ограничений // Безопасные информационные технологии: Сб. трудов 11-й Междунар. науч.-технич. конф. М.: МГТУ им. Н.Э. Баумана, 2021. С. 85-90.
Кнут Д. Э. Искусство программирования. Т. 1: Основные алгоритмы. 3-е изд. М.: Издательский дом "Вилвямс", 2002. 720 с.
О среднем числе допустимых решений в задаче о рюкзаке | Прикладная дискретная математика. 2025. № 68. DOI: 10.17223/20710410/68/7
Скачать полнотекстовую версию
Загружен, раз: 70