Визначення. Найпоширенішою задачею, яку розв’язують, є задача про рюкзак 0-1, яка обмежує кількість копій кожного типу елемента до нуля або однієї. Дано набір елементів, пронумерованих від 1 до, кожен з яких має вагу та значення, а також максимальну ємність ваги, максимізувати відповідно до та .
Проблему рюкзака 0/1 можна визначити наступним чином: нам дано N предметів, де кожен предмет має певну вагу (wi) і цінність (vi), пов’язану з ним. Нам також дається мішок ємністю W. Мета полягає в тому, щоб помістити предмети в мішок так, щоб сума пов’язаних з ними значень була максимально можливою.
Дано N предметів, де кожен предмет має певну вагу та прибуток, а також дано мішок ємністю W, [тобто мішок може вмістити щонайбільше W ваги]. Завдання полягає в тому, щоб покласти предмети в сумку так, щоб сума пов'язаних з ними прибутків була максимально можливою.
У проблемі ранця, вам потрібно упакувати набір предметів із заданими значеннями та розмірами (наприклад, вагою або об’ємом) у контейнер із максимальною місткістю . Якщо загальний розмір предметів перевищує ємність, ви не можете упакувати їх усі.
Застосуйте рішення на основі динамічного програмування для вирішення проблеми ранця 0-1. Нам дано вагу набору предметів {6, 3, 3, 2, 2, 2} і рюкзак ємністю W=10. Ми повинні наповнити цей рюкзак, розглядаючи його як рюкзак 0-1. Цей метод має часову складність O(N*W).
Пояснення: проблему з рюкзаком 0-1 неможливо вирішити жадібним методом, оскільки можливе заповнення рюкзака на повну ємність тому тут жадібний алгоритм не є оптимальним.