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

от Уикипедия, свободната енциклопедия
Направо към навигацията Направо към търсенето

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

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

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

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

Приложения[редактиране | редактиране на кода]

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

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

Пример[редактиране | редактиране на кода]

Knapsack.svg

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

Задача
Нека е дадена раница, която издържа до 15 kg. Нека имаме пет предмета, съответно:
  • зелена кутия с тегло 12 kg и стойност 4 долара,
  • сива кутия с тегло 1 kg и стойност 2 долара,
  • жълта кутия с тегло 4 kg и стойност 10 долара,
  • розова кутия с тегло 1 kg и стойност 1 долар,
  • синя кутия с тегло 2 kg и стойност 2 долара.
Кои кутии следва да бъдат избрани, за да се максимизира стойността на предметите в раницата, докато е изпълнено ограничението теглото на предметите да не превишава общо 15 kg?
Решение
Ако от всеки вид кутии има налични произволен брой, то решението е да се изберат три жълти кутии и три сиви кутии. Ако от всеки вид кутии е налична само по една (показаната), то решението е да се изберат всички кутии с изключение на зелената.
Забележка
Многопараметричен вариант на задачата би отчитал не само теглото, но и обема на кутиите.

Източници[редактиране | редактиране на кода]

  1. Mathews, G. B.. On the partition of numbers. // Proceedings of the London Mathematical Society 28. 25 June 1897. DOI:10.1112/plms/s1-28.1.486. с. 486–490.
  2. а б Dantzig, Tobias. Numbers: The Language of Science, 1930.
Криейтив Комънс - Признание - Споделяне на споделеното Лиценз за свободна документация на ГНУ Тази страница частично или изцяло представлява превод на страницата „Knapsack problem“ в Уикипедия на английски. Оригиналният текст, както и този превод, са защитени от Лиценза „Криейтив Комънс - Признание - Споделяне на споделеното“, а за съдържание, създадено преди юни 2009 година — от Лиценза за свободна документация на ГНУ. Прегледайте историята на редакциите на оригиналната страница, както и на преводната страница. Вижте източниците на оригиналната статия, състоянието ѝ при превода, и списъка на съавторите.