Курсовая работа: Задача о рюкзаке (также задача о ранце) — NP-полная задача комбинаторной оптимизации.

Введение

Задача о рюкзаке (также задача о ранце) — NP-полная задача комбинаторной оптимизации.
Задача о рюкзаке — это задача оптимизации, используемая для иллюстрации как проблемы, так и решения. Он получил свое название от сценария, в котором человек ограничен в количестве предметов, которые можно поместить в рюкзак фиксированного размера. Учитывая набор предметов с определенным весом и ценностью, цель состоит в том, чтобы получить как можно больше ценности в рюкзаке с учетом ограничения веса рюкзака.
Задача о рюкзаке — это пример задачи комбинированной оптимизации, тема математики и информатики о поиске оптимального объекта среди множества объектов. Это проблема, которая изучается более века и является часто используемым примером задачи комбинаторной оптимизации, когда требуется оптимальный объект или окончательное решение, когда исчерпывающий поиск невозможен. Проблема может быть обнаружена в сценариях реальной жизни, таких как распределение ресурсов в условиях финансовых ограничений или даже при выборе инвестиций и портфелей. Его также можно найти в таких областях, как прикладная математика, теория сложности, криптография, комбинаторика и информатика. Это самая важная проблема в логистике.
В задаче о рюкзаке у заданных предметов есть как минимум два атрибута: стоимость предмета, которая влияет на его важность, и вес или объем предмета, который является его ограничивающим аспектом. Поскольку исчерпывающий поиск невозможен, можно разбить проблемы на более мелкие подзадачи и выполнять их рекурсивно. Такая структура называется оптимальной. Это относится только к одному предмету за раз и текущему весу, который все еще доступен в рюкзаке. Решателю проблемы нужно только решить, брать предмет или нет, исходя из веса, который еще можно взять. Однако, если это программа, пересчет не является независимым и вызовет проблемы. Здесь можно применить методы динамического программирования. Решения каждой подзадачи сохраняются, так что вычисление нужно выполнить только один раз.
Задача о рюкзаке (также задача о ранце) — NP-полная задача комбинаторной оптимизации.
Задача о рюкзаке — это пример задачи комбинированной оптимизации, тема математики и информатики о поиске оптимального объекта среди множества объектов. Это проблема, которая изучается более века и является часто используемым примером задачи комбинаторной оптимизации, когда требуется оптимальный объект или окончательное решение, когда исчерпывающий поиск невозможен. Проблема может быть обнаружена в сценариях реальной жизни, таких как распределение ресурсов в условиях финансовых ограничений или даже при выборе инвестиций и портфелей. Его также можно найти в таких областях, как прикладная математика, теория сложности, криптография, комбинаторика и информатика. Это самая важная проблема в логистике.
В общем виде задачу можно сформулировать так: из заданного множества предметов со свойствами «стоимость» и «вес» требуется отобрать подмножество с максимальной полной стоимостью, соблюдая при этом ограничение на суммарный вес.

• Актуальность темы исследования

Классическая задача о ранце (КЗР) относится к числу широко известных задач дискретной оптимизации. Впервые КЗР была сформулирована Д. Данцигом и с тех пор активно исследуется; ее популярность, прежде всего, вызвана большим количеством приложений. Основные сферы применения находятся в областях планирования и управления экономическими, производственными и транспортными системами. В частности, следует отметить формулируемые в рамках КЗР задачи объемного планирования для предприятий с единичным и мелкосерийным характером производства и задачи загрузки транспортных средств.
Начиная с 60-70-х гг. ХХ века стали рассматриваться