Визначення. Найпоширенішою задачею, яку розв’язують, є задача про рюкзак 0-1, яка обмежує кількість копій кожного типу елемента до нуля або однієї. Дано набір елементів, пронумерованих від 1 до, кожен з яких має вагу та значення, а також максимальну ємність ваги, максимізувати відповідно до та .
Проблему рюкзака 0/1 можна визначити наступним чином: нам дано N предметів, де кожен предмет має певну вагу (wi) і цінність (vi), пов’язану з ним. Нам також дається мішок ємністю W. Мета полягає в тому, щоб помістити предмети в мішок так, щоб сума пов’язаних з ними значень була максимально можливою.
У проблемі ранця, вам потрібно упакувати набір предметів із заданими значеннями та розмірами (наприклад, вагою або об’ємом) у контейнер із максимальною місткістю . Якщо загальний розмір предметів перевищує ємність, ви не можете упакувати їх усі.
Проблема необмеженого рюкзака: чим вона відрізняється від 0/1. На відміну від попередніх проблем, Проблема необмеженого рюкзака дозволяє використовувати необмежену кількість кожного предмета. Це означає, що якщо предмет можна вибрати, ви можете вибрати той самий предмет стільки разів, скільки потрібно, доки не буде порушено вагу.
Проблема 0-1 з кількома рюкзаками є розширенням добре відомої проблеми з рюкзаками 0-1. Це проблема призначення m об’єктів, кожен з яких має значення та вагу, до n рюкзаків таким чином, щоб загальна вага в кожному рюкзаку була меншою за межу його місткості, а загальна вартість у рюкзаках була максимальною.
Пояснення: проблему з рюкзаком 0-1 неможливо вирішити жадібним методом, оскільки можливе заповнення рюкзака на повну ємність тому тут жадібний алгоритм не є оптимальним.