![cover image](https://wikiwandv2-19431.kxcdn.com/_next/image?url=https://upload.wikimedia.org/wikipedia/commons/thumb/f/fd/Knapsack.svg/languk-640px-Knapsack.svg.png&w=640&q=50)
Задача пакування рюкзака
З Вікіпедії, безкоштовно encyclopedia
Задача пакування рюкзака (англ. Knapsack problem) — задача комбінаторної оптимізації: для заданої множини предметів, кожен з яких має вагу і цінність, визначити яку кількість кожного з предметів слід взяти, так, щоб сумарна вага не перевищувала задану, а сумарна цінність була максимальною. Задача бере свою назву від доволі відомої ситуації, коли потрібно наповнити рюкзак, що здатен витримати деяку максимальну масу, предметами, кожен з яких має вартість (або корисність) та масу. Необхідно обрати об'єкти в такий спосіб, аби максимізувати сумарну вартість (або користь), але не перевищити максимально припустиму масу.
![Thumb image](http://upload.wikimedia.org/wikipedia/commons/thumb/f/fd/Knapsack.svg/320px-Knapsack.svg.png)
Задача часто виникає при розподілі ресурсів, коли наявні фінансові обмеження, і вивчається в таких областях, як комбінаторика, інформатика, теорія складності, криптографія, прикладна математика.
Описання задачі досить просте, але розв'язання — складне. Відомі алгоритми, на практиці, здатні розв'язати задачі досить великих розмірів. Однак, унікальне формулювання задачі, а також той факт, що вона присутня як підзадача у більших, загальніших проблемах, робить її важливою для наукових досліджень.