UK 
EnglishТипова
Polski🎒 Рюкзак 0/1
Максимізуйте цінність, не перевищивши місткість. Дивіться, як динамічне програмування заповнює таблицю dp за рекурентністю «взяти-чи-пропустити», потім відновлює оптимальний набір — і чому жадібний підхід може схибити.
Про задачу рюкзака 0/1
Задача рюкзака 0/1 — класична задача комбінаторної оптимізації: маючи n предметів, кожен з вагою wᵢ та цінністю vᵢ, потрібно обрати підмножину, що максимізує сумарну цінність, не перевищуючи місткість W. Позначка «0/1» означає, що кожен предмет береться повністю або не береться зовсім — часткового вибору немає. Задача є NP-складною: жоден відомий алгоритм не розв'язує всі випадки за поліноміальний час, але підхід динамічного програмування (DP) працює за O(nW) псевдополіноміального часу і знаходить точний оптимум.
У цій симуляції можна додавати, редагувати чи видаляти предмети та спостерігати, як таблиця DP заповнюється комірка за коміркою: кожна комірка dp[i][w] зберігає максимальну цінність, досяжну з перших i предметів за місткості w. Після заповнення таблиці етап зворотного відстеження (backtracking) відновлює оптимальний вибір предметів, підсвічений у сітці, а порівняння поруч показує, чим жадібна дробова евристика відрізняється від точного розв'язку DP.
Поширені запитання
Яке рекурентне співвідношення для DP рюкзака 0/1?
dp[i][w] = max(dp[i−1][w], dp[i−1][w − wᵢ] + vᵢ), якщо wᵢ ≤ w, інакше dp[i−1][w]. Перший доданок пропускає предмет i; другий бере його (можливо, лише якщо його вага влазить). Базовий випадок: dp[0][w] = 0 для всіх w. Кінцева відповідь — dp[n][W].
Чому задача рюкзака 0/1 називається NP-складною?
NP-складність означає, що не відомо жодного поліноміального алгоритму, який розв'язує всі випадки. Підхід DP працює за O(nW) часу, але саме W може бути експоненційно великим у своєму двійковому представленні (псевдополіноміальний, а не справді поліноміальний час). Карп довів NP-повноту задачі 1972 року, звівши її до задачі суми підмножини. На практиці для помірних W (до мільйонів) DP цілком реалізовний.
Чим жадібний дробовий рюкзак відрізняється від версії 0/1?
Дробовий рюкзак дозволяє ділити предмети; жадібна стратегія — завжди брати предмет із найвищим співвідношенням цінність/вага (vᵢ/wᵢ) — дає оптимальний розв'язок за O(n log n). Для рюкзака 0/1 такий жадібний підхід може схибити: наприклад, за місткості 10 і предметів (вага 6, цінність 6), (вага 5, цінність 5) та (вага 5, цінність 5), жадібний за співвідношенням обере предмет 1 з цінністю 6, тоді як узяття предметів 2 і 3 дає цінність 10.
Як відновити оптимальні предмети після заповнення таблиці DP?
Починаючи з комірки dp[n][W], порівняйте її з dp[n−1][W]. Якщо вони відрізняються, предмет n було включено; відніміть його вагу від W і перейдіть до рядка n−1. Якщо вони однакові, предмет n було виключено; перейдіть до dp[n−1][W]. Повторюйте до рядка 0. Цей прохід зворотного відстеження виконується за O(n).
Чи можна зменшити просторову складність нижче O(nW)?
Так. Оскільки dp[i][w] залежить лише від рядка i−1, можна використати два одновимірних масиви довжини W+1 (поточний і попередній рядок), зменшивши пам'ять до O(W). Якщо перебирати w від W до wᵢ в одному одновимірному масиві, можна досягти O(W) пам'яті на місці без збереження попередніх рядків, хоча зворотне відстеження тоді вимагає повторного обчислення або збереження різниць рядків.
Що таке метод гілок і меж для рюкзака?
Метод гілок і меж досліджує експоненційне дерево рішень «включити/виключити», але відсікає піддерева, чия верхня межа (зазвичай дробова релаксація) не може перевершити поточний найкращий розв'язок. Для багатьох практичних випадків це набагато швидше за DP, коли W величезне, а n мале. Це основа комерційних розв'язувачів цілочисельного програмування, таких як Gurobi та CPLEX.
Чи існують наближені алгоритми для рюкзака?
Так. Повністю поліноміальна апроксимаційна схема (FPTAS) дає розв'язок у межах множника (1 − ε) від оптимального за O(n²/ε) часу, масштабуючи й округлюючи цінності предметів. Це робить таблицю DP достатньо малою для великих W, гарантуючи майже оптимальні результати, і є знаковим результатом теорії апроксимації.
Які практичні застосування має задача рюкзака?
Застосування включають завантаження вантажів (максимізація доходу за обмеження ваги літака), розподіл ресурсів (розподіл CPU/пам'яті між задачами), формування портфеля (максимізація прибутку за обмеженого бюджету), криптографію (ранні криптосистеми з відкритим ключем на основі рюкзака Меркла-Геллмана, нині зламані) та розподіл регістрів у компіляторах.
Чим відрізняється варіант із кількома рюкзаками?
У задачі з кількома рюкзаками є m рюкзаків, кожен зі своєю місткістю, і предмети мають бути призначені щонайбільше одному рюкзаку. Це узагальнює задачу пакування в контейнери і є суттєво складнішим; оптимальні розв'язки вимагають цілочисельного лінійного програмування або евристик на кшталт «спочатку найбільший, що влазить». Це трапляється в логістиці, розподілі віртуальних машин у хмарі та задачах розкрою.
Що таке необмежена задача рюкзака?
У необмеженому варіанті кожен предмет можна обирати будь-яку кількість разів (необмежений запас). Рекурентність змінюється на dp[w] = max за всіма i, де wᵢ ≤ w, від (dp[w − wᵢ] + vᵢ), використовуючи один одновимірний масив, що перебирається вперед від w = 1 до W. Це моделює такі сценарії, як розмін монет або розрізання стрижня на частини для максимізації прибутку.