Метод таблиц допустимых решений в задаче о ранце

Владимир Николаевич Бурков, Всеволод Олегович Корепанов, Александр Рудольфович Кашенков

Аннотация


Предложен новый подход к получению верхних и нижних оценок для задачи о ранце, в основе которого лежат операции «склеивания» решений одного слоя (k-слоем называется множество решений, у которых определены первые k компонент, соответствующих предметам). Рассмотрены две операции склеивания. При первой операции склеивания не теряется ни одно из допустимых решений, но могут появиться недопустимые. При этом мы получаем верхнюю оценку решений задачи. Во второй операции остаются только допустимые решения, но не все. При этом мы получаем нижнюю оценку решений задачи. В статье представлены результаты численных экспериментов по оценке времени и точности предлагаемого подхода в зависимости от объёма входных данных, объёма рюкзака и величины склеивания.


Ключевые слова


задача о ранце; верхняя и нижняя оценки решений; вычислительный эксперимент

Полный текст:

PDF

Литература


Diakaki, C. Towards a multi-objective optimization approach for improving energy efficiency in buildings / C. Diakaki, E. Grigoroudis, D. Kolokotsa // Energy and Buildings. – 2008. – Vol. 40, no. 9. – P. 1747–1754. DOI: 10.1016/j.enbuild.2008.03.002

Dynamic placement for clustered web applications / A. Karve, T. Kimbrel, G. Pacifici et al. // Proceedings of the 15th international conference on World Wide Web, WWW '06. – 2006. – P. 595–604. DOI: 10.1145/1135777.1135865

Gatzianas, M. Control of wireless networks with rechargeable batteries / M. Gatzianas, L. Georgiadis, L. Tassiulas // IEEE Transactions on Wireless Communications. – 2010. – Vol. 9, no. 2. – P. 581–593. DOI: 10.1109/TWC.2010.080903

Новый эффективный алгоритм решения задачи об инвестициях / Е.Р. Гафаров, А. Долгий, А.А. Лазарев, Ф. Вернер // Автоматика и телемеханика. – 2016. – № 9. – С. 150–166.

Загурских, Е.А. Разработка и реализация криптографической системы с открытым ключом, основанной на обобщении задачи о ранце для кольца многочленов с коэффициентами из поля: выпускная квалификационная работа магистра / Е.А.Загурских. – Новосибирск: Новосибирский государственный университет, 2017. – 24 с.

Martello, S. New trends in exact algorithms for the 0–1 knapsack problem / S. Martello, D. Pisinger, P. Toth // European Journal of Operational Research. – 2000. – Vol. 123, no. 2. – P. 325– 332. DOI: 10.1016/s0377-2217(99)00260-x

Kellerer, H. Knapsack Problems / H. Kellerer, U. Pferschy, D. Pisinger. – Springer-Verlag Berlin Heidelberg, 2004. ISBN 3-540-40286-1. MR 2161720. DOI: 10.1007 / 978-3-540-24777-7

Метод допустимых решений в многомерной задаче о ранце / В.Н.Бурков, И.В. Буркова, Б.К. Уандыков, Д.С. Чу // Экономика и менеджмент систем управления. – 2015. – Т.18, № 4.1. – С. 136–144.




DOI: http://dx.doi.org/10.14529/ctcr180204

Ссылки

  • На текущий момент ссылки отсутствуют.