The characteristics of solutions to the bounded knapsack problem are analyzed. Expressions are derived for calculating the average value of the objective function among all feasible solutions, as well as formulas linking the number of solutions with subproblems of lower dimension. For cases where variables take values from the set {0,1} OR {0,1, 2}, formulas are defined for estimating the average number of feasible solutions in all problems of a given dimension with limited values of the weight coefficients. A generating function is considered that describes the number of solutions to knapsack problems of a fixed dimension, where the components of the weight vector belong to a given range. The results obtained can be useful in analyzing the computational complexity of algorithms for solving the knapsack problem.
Download file
Counter downloads: 6
- Title On the average number of solutions in the knapsack problem
- Headline On the average number of solutions in the knapsack problem
- Publesher
Tomsk State University - Issue Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics 68
- Date:
- DOI 10.17223/20710410/68/7
Keywords
knapsack problem, generating functions, dynamic programming, NP-complete problems, coefficient methodAuthors
References
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 с.
On the average number of solutions in the knapsack problem | Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics. 2025. № 68. DOI: 10.17223/20710410/68/7
Download full-text version
Counter downloads: 68