О некоторых комбинаторных свойствах задачи о рюкзаке

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