Задача за раницата

Задачата за раницата (на английски: knapsack problem, rucksack problem) е задача за комбинаторна оптимизация, която гласи следното: Ако са дадени различни видове предмети, всеки с определена тежест и цена, да се определи броят предмети от всеки вид, чиято сумарна тежест е по-малка или равна на определено число, и чиято сумарна цена е възможно най-висока. Името си задачата получава от ситуацията, в която някой трябва да напълни ограничена по размери раница с най-ценните възможни предмети.

Проблемът често възниква при разпределението на ресурси в условия на финансови ограничения и е обект на изследване в области като комбинаторика, компютърни науки, математическа оптимизация, теория на изчислителната сложност, криптография. Задачата за раницата е изследвана в продължение на повече от век, като ранните трудове датират от 1897 година.^[1] Самото название „задача за раницата“ е дадено в ранните трудове на математика Тобиас Данциг (1884–1956),^[2] като препратка към обичайния проблем да се опаковат най-ценните или полезни предмети в раница без да се надвишават ограниченията ѝ за обем или издръжливост.^[2]

Задачата за раницата представлява интерес в областта на компютърните науки по множество причини:

• Задача за вземане на решение от този вид е NP-пълна, следователно няма известен алгоритъм, който във всички случаи да може да я реши едновременно бързо (за полиномиално време) и коректно.
• При все че задачата е NP-пълна, оптимизационната задача е NP-сложна, и няма известен полиномиален алгоритъм, който при дадено решение може да отговори на въпроса дали това е оптималното решение (т.е. няма решение с по-голяма сумарна цена на стойността), което решава NP-пълната задача за вземане на решение.

Приложения

Едно изследване от 1998 година на хранилището с алгоритми на университета „Стоуни Бруук“ показва, че от общо 75 алгоритмични задачи, задачата за раницата е 18-ата най-популярна задача и четвъртата най-необходима за решаване при задачи за k-мерни дървета, суфиксни дървета и др.

Задачи за раница се появяват в широк кръг реални ситуации за вземане на решения, например откриване на оптимално разпределение на ресурси без загуба, избор на инвестиции и финансови портфолиа, избор на активи за застраховане, генериране на ключове за криптосистеми, генериране на изпитни варианти от различни по сложност задачи и оценяване на представянето на студенти.

Пример

Пример на еднопараметричен вариант на задачата за раницата (т.е. с едно ограничение).

Задача

Нека е дадена раница, която издържа до 15 kg. Нека имаме пет предмета, съответно:

• зелена кутия с тегло 12 kg и стойност 4 долара,
• сива кутия с тегло 1 kg и стойност 2 долара,
• жълта кутия с тегло 4 kg и стойност 10 долара,
• розова кутия с тегло 1 kg и стойност 1 долар,
• синя кутия с тегло 2 kg и стойност 2 долара.

Кои кутии следва да бъдат избрани, за да се максимизира стойността на предметите в раницата, докато е изпълнено ограничението теглото на предметите да не превишава общо 15 kg?

Решение

Ако от всеки вид кутии има налични произволен брой, то решението е да се изберат три жълти кутии и три сиви кутии. Ако от всеки вид кутии е налична само по една (показаната), то решението е да се изберат всички кутии с изключение на зелената.

Забележка

Многопараметричен вариант на задачата би отчитал не само теглото, но и обема на кутиите.