Задача за раницата
Задачата за раницата (на английски: 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?
- Решение
- Ако от всеки вид кутии има налични произволен брой, то решението е да се изберат три жълти кутии и три сиви кутии. Ако от всеки вид кутии е налична само по една (показаната), то решението е да се изберат всички кутии с изключение на зелената.
- Забележка
- Многопараметричен вариант на задачата би отчитал не само теглото, но и обема на кутиите.
Източници
[редактиране | редактиране на кода]- ↑ Mathews, G. B. On the partition of numbers // Proceedings of the London Mathematical Society 28. 25 юни 1897. DOI:10.1112/plms/s1-28.1.486. с. 486–490.
- ↑ а б Dantzig, Tobias. Numbers: The Language of Science, 1930.
 
|
Тази страница частично или изцяло представлява превод на страницата Knapsack problem в Уикипедия на английски. Оригиналният текст, както и този превод, са защитени от Лиценза „Криейтив Комънс – Признание – Споделяне на споделеното“, а за съдържание, създадено преди юни 2009 година – от Лиценза за свободна документация на ГНУ. Прегледайте историята на редакциите на оригиналната страница, както и на преводната страница, за да видите списъка на съавторите.
ВАЖНО: Този шаблон се отнася единствено до авторските права върху съдържанието на статията. Добавянето му не отменя изискването да се посочват конкретни източници на твърденията, които да бъдат благонадеждни. |