• A
  • A
  • A
  • ABC
  • ABC
  • ABC
  • А
  • А
  • А
  • А
  • А
Regular version of the site

Article

Верхняя оценка сложности одного из вариантов метода ветвей и границ для задачи о сумме подмножеств

Колпаков Р., Посыпкин М. А., Тант Син С. Т.

In the paper we obtain an upper bound for the complexity of solving the subset sum problem which is a particular case of the knapsack problem by one of the variants of the branch-and-bound method with an additional pruning rule based on the comparison of the maximum and minimum number of items that can be put into the knapsack. As auxiliary results, we establish various combinatorial properties of subproblems processed for solving the subset sum problem by the considered variant of the branch-and-bound method.