RUS  ENG
Полная версия
ЖУРНАЛЫ // Автоматика и телемеханика // Архив

Автомат. и телемех., 1995, выпуск 7, страницы 124–130 (Mi at3682)

Развивающиеся системы

Эффективный алгоритм решения одного частного случая обобщенной задачи о камнях

В. Н. Бурковa, С. И. Дзюбкоa, А. А. Ягуповb

a Институт проблем управления РАН, г. Москва
b АО "Руссинко", Москва

Аннотация: Рассматривается эффективный метод решения частного случая классической “задачи о камнях”. Задача заключается в распределений $n$ различных объектов (камней) на $m$ групп (куч) так, чтобы суммарные объемы всех групп были по возможности равны. Рассматривается случай, когда объемы упорядочены так, что объем $j$-го объекта описывается многочленом степени $\alpha$. Предлагается алгоритм решения для случая $n\equiv 0$ ($\operatorname{mod} 2m^{\alpha}$) с оценкой времени счета $O(n)$. Рассматривается также ряд обобщений этой задачи.

УДК: 519.854.2


Поступила в редакцию: 29.09.1994


 Англоязычная версия: Automation and Remote Control, 1995, 56:7, 1011–1016

Реферативные базы данных:


© МИАН, 2024