Зміст:
Визначення - Що означає проблема "Рюкзак"?
Проблема з рюкзаком - це проблема оптимізації, яка використовується для ілюстрації як проблеми, так і рішення. Він отримує свою назву за сценарієм, коли один обмежений у кількості предметів, які можна помістити всередину рюкзака фіксованого розміру. Враховуючи набір предметів із конкретною вагою та значеннями, мета полягає в тому, щоб отримати якомога більше значення в рюкзаку, враховуючи обмеження ваги рюкзака.
"Техопедія" пояснює проблему "Рюкзак"
Проблема з рюкзаком є прикладом комбінаційної проблеми оптимізації, теми з математики та інформатики про пошук оптимального об'єкта серед набору об’єктів. Це проблема, яка вивчається вже більше століття, і є загальновживаною прикладною проблемою комбінаторної оптимізації, коли існує потреба в оптимальному об'єкті чи кінцевому вирішенні, коли вичерпний пошук неможливий. Проблему можна знайти в реальних сценаріях, таких як розподіл ресурсів у фінансових обмеженнях або навіть у виборі інвестицій та портфелів. Його також можна знайти в таких галузях, як прикладна математика, теорія складності, криптографія, комбінаторика та інформатика. Це легко найважливіша проблема в логістиці.
У проблемі з рюкзаком дані предмети мають як мінімум два атрибути - значення предмета, яке впливає на його значення, та вагу або об’єм предмета, що є його аспектом обмеження. Оскільки вичерпний пошук неможливий, можна розбити проблеми на менші субпроблеми та запустити їх рекурсивно. Це називається оптимальною підструктурою. Це стосується лише одного предмета за раз і поточної ваги, яка все ще доступна в рюкзаку. Вирішувач проблеми повинен вирішити, брати предмет чи ні, виходячи з ваги, яку все ще можна прийняти. Однак, якщо це програма, повторне обчислення не є незалежним і може спричинити проблеми. Тут можна застосувати динамічні методи програмування. Рішення кожної підзадачі зберігаються так, що обчислення потрібно було б здійснити лише один раз.
