Задачата за раницата (на английски: 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?
- Решение
- Ако от всеки вид кутии има налични произволен брой, то решението е да се изберат три жълти кутии и три сиви кутии. Ако от всеки вид кутии е налична само по една (показаната), то решението е да се изберат всички кутии с изключение на зелената.
- Забележка
- Многопараметричен вариант на задачата би отчитал не само теглото, но и обема на кутиите.
Wikiwand in your browser!
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.
