0/1 Виправлення проблеми з рюкзаком за допомогою прикладу динамічного програмування

Що таке проблема ранця?

Команда Проблема з ранцем – це класична задача комбінаторної оптимізації. Супермаркет зберігає n пакети (n ≤ 100). Пакет i має вагу W[i] ≤ 100 та значення V[i] ≤ 100. Злодій не може переносити вагу, що перевищує місткість M (M ≤ 100). Які посилки повинен взяти злодій, щоб максимізувати загальну вартість?

Вхідний сигнал:

• Максимальна вага М і кількість упаковок n.
• Масив ваги W[i] і відповідного значення V[i].

вихід:

• Максимальне загальне значення, яке можна отримати в межах місткості.
• Точний набір посилок, які має взяти злодій.

Алгоритм Knapsack поділяється на два добре відомі варіанти:

• 0/1 Проблема з рюкзаком вирішується за допомогою динамічного програмування. Кожен пакет або береться цілком, або залишається — без дробових частин та дублікатів.
• Задача про дробовий ранець вирішується за допомогою жадібної стратегії. Тут ви можете взяти частину будь-якого пакета, щоб заповнити решту місткості.

Як вирішити проблему ранця за допомогою динамічного програмування з прикладом

Метод «розділяй і володарюй» розбиває велику проблему на підзадачі, а потім продовжує розбивати, доки кожна підзадача не стане простою. Однак проста рекурсія часто вирішує одну й ту саму підзадачу багато разів і марнує роботу.

Основна ідея динамічного програмування Knapsack полягає в тому, щоб зберігати кожну розв'язану підзадачу в таблиці. Повторні виклики зчитують відповідь замість її переобчислення, перетворюючи експоненціальну рекурсію на код, що обчислюється за поліноміальний час.

Вирішіть задачу про рюкзак за допомогою динамічного програмування

Щоб розробити рішення динамічного програмування, потрібно виконати чотири кроки:

• Спочатку розв'яжіть найменші підзадачі.
• Виведіть рекурентність, яка будує відповідь підзадачі з менших.
• Зберігайте відповіді на підзадачі в таблиці, обчисленій знизу вгору з використанням рекурентності.
• Зберіть остаточну відповідь з повністю заповненої таблиці.

Проаналізуйте проблему ранця 0/1

Оптимальне значення залежить від двох незалежних факторів:

1. Скільки пакетів все ще розглядається.
2. Решту ваги рюкзак все ще може вмістити.

Оскільки цільова функція залежить від двох величин, таблиця опцій має бути двовимірною. Нехай B[i][j] позначає максимальне значення при виборі серед пакетів {1, …, i} з обмеженням ваги j.

• Остаточна відповідь така B[n][M], найкраще загальне значення для всіх n пакетів за місткості M.
• Загальна вибрана вага завжди обмежена поточною вантажопідйомністю: B[i][j] ≤ j.

Приклад: якщо B[4][10] = 8, найкраща загальна вага з перших чотирьох упаковок місткістю до 10 дорівнює 8. Деякі з цих чотирьох упаковок можуть бути пропущені.

Формула для обчислення B[i][j]

• W[i], V[i] – вага та вартість i-го пакета, де i знаходиться в {1, …, n}.
• M – це максимальна вага, яку може витримати рюкзак.

Базовий випадок з одним пакетом: для кожної ємності j ≥ W[1]:

B[1][j] = W[1]

Для загального випадку вирішіть, чи включати пакет i до ємності j:

• Якщо пакет i є пропустив, B[i][j] дорівнює найкращому значенню з використанням пакетів {1, …, i-1} за ємністю j:

B[i][j] = B[i - 1][j]

• Якщо пакет i є прийняті (дозволено лише тоді, коли W[i] ≤ j), B[i][j] дорівнює V[i] плюс найкраще значення з пакетів {1, …, i-1} під ємністю j – W[i]:

B[i][j] = V[i] + B[i - 1][j - W[i]]

Візьмемо більшого з двох кандидатів.

Основи динамічного програмування

Поєднання двох випадків дає повну рекурентність:

B[i][j] = max(B[i - 1][j], V[i] + B[i - 1][j - W[i]])

Базовий випадок такий B[0][j] = 0 для кожного j, оскільки нуль пакетів дають нульове значення незалежно від ємності.

Розрахувати таблицю параметрів

Побудуйте B, використовуючи рекурентність. Після заповнення B, та сама таблиця керує trace-back, який реконструює вибрані пакети. Таблиця B має n + 1 рядків та M + 1 стовпців:

• Рядок 0 – це базовий випадок, заповнений нулями.
• Використовуйте рядок 0 для обчислення рядка 1, рядок 1 для обчислення рядка 2 і продовжуйте, доки рядок n не буде завершено.

Таблиця параметрів

Trace

Після завершення B зосередьтеся на B[n][M], оптимальне загальне значення для всіх n пакетів місткістю M.

• If B[n][M] = B[n-1][M], пакет n не було вибрано, тому продовжуйте tracвід B[n-1][M].
• If B[n][M] ≠ B[n-1][M], пакет n було вибрано, тож продовжуйте tracвід B[n-1][M – W[n]].

Повторюйте, доки не дійдете до рядка 0 таблиці.

Алгоритм пошуку таблиці параметрів для пошуку вибраних пакетів

Примітка: щоразу, коли B[i][j] = B[i-1][j], пакет i не вибрано. Значення B[n][M] – оптимальна загальна вартість, упакована в рюкзак.

Кроки для tracобрані пакети:

• Крок 1: Почніть з i = n, j = M.
• Крок 2: Скануйте стовпець j знизу вгору, доки не знайдете рядок i, де B[i][j] > B[i-1][j]. Позначте пакет i як вибраний: Select[i] = true.
• Крок 3: Оновлення j = j – W[i]. Якщо j > 0, поверніться до кроку 2, інакше перейдіть до кроку 4.
• Крок 4: Роздрукувати кожен пакет, позначений як вибраний.

Java Code

Наступні Java Метод заповнює B[][] знизу вгору, друкує таблицю для перевірки, а потім tracвибрані пакети.

public void knapsackDyProg(int W[], int V[], int M, int n) {
    int B[][] = new int[n + 1][M + 1];

    for (int i = 0; i <= n; i++)
        for (int j = 0; j <= M; j++) {
            B[i][j] = 0;
        }

    for (int i = 1; i <= n; i++) {
        for (int j = 0; j <= M; j++) {
            B[i][j] = B[i - 1][j];

            if ((j >= W[i - 1]) && (B[i][j] < B[i - 1][j - W[i - 1]] + V[i - 1])) {
                B[i][j] = B[i - 1][j - W[i - 1]] + V[i - 1];
            }

            System.out.print(B[i][j] + " ");
        }
        System.out.print("\n");
    }

    System.out.println("Max Value:\t" + B[n][M]);
    System.out.println("Selected Packs: ");

    int j = M;
    while (n != 0) {
        if (B[n][j] != B[n - 1][j]) {
            System.out.println("\tPackage " + n + " with W = " + W[n - 1] + " and Value = " + V[n - 1]);
            j = j - W[n - 1];
        }
        n--;
    }
}

Функція napsackDyProg() в Java

Пояснення коду:

1. Розмістити таблицю B[][] та ініціалізувати кожну комірку значенням 0.
2. Заповніть B[][] знизу вгору, використовуючи рекурентність з попереднього розділу.
3. Почніть кожну клітинку зі значення «пропустити пакет i» B[i-1][j].
4. Якщо вибір пакета i є можливим і дає чітко краще значення, перезапишіть комірку.
5. Tracвибрані елементи з рядка n назад до рядка 0.
6. Щоразу, коли вибрано пакет n, зменшіть залишкову ємність на W[n-1].

Виправлення примітки: змінений параметр оригінального фрагмента коду M ще читаючи B[n][M]У безпечнішій версії вище використовується окремий курсор. j для trace.

Команда Java Водій запускає алгоритм на двох оброблених прикладах:

public void run() {
    // First Example
    // int W[] = new int[]{3, 4, 5, 9, 4};
    // int V[] = new int[]{3, 4, 4, 10, 4};
    // int M = 11;

    // Second Example
    int W[] = new int[]{12, 2, 1, 1, 4};
    int V[] = new int[]{4, 2, 1, 2, 10};
    int M = 15;

    int n = V.length;
    knapsackDyProg(W, V, M, n);
}

Вивід для першого прикладу:

0 0 0 3 3 3 3 3 3 3 3 3
0 0 0 3 4 4 4 7 7 7 7 7
0 0 0 3 4 4 4 7 7 8 8 8
0 0 0 3 4 4 4 7 7 10 10 10
0 0 0 3 4 4 4 7 8 10 10 11
Max Value:	11
Selected Packs:
	Package 5 with W = 4 and Value = 4
	Package 2 with W = 4 and Value = 4
	Package 1 with W = 3 and Value = 3

Вивід для другого прикладу:

0 0 0 0 0 0 0 0 0 0 0 0 4 4 4 4
0 0 2 2 2 2 2 2 2 2 2 2 4 4 6 6
0 1 2 3 3 3 3 3 3 3 3 3 4 5 6 7
0 2 3 4 5 5 5 5 5 5 5 5 5 6 7 8
0 2 3 4 10 12 13 14 15 15 15 15 15 15 15 15
Max Value:	15
Selected Packs:
	Package 5 with W = 4 and Value = 10
	Package 4 with W = 1 and Value = 2
	Package 3 with W = 1 and Value = 1
	Package 2 with W = 2 and Value = 2

Часово-просторова складність рюкзака 0/1

• Часова складність: O(n · M) — два вкладені цикли переміщують n елементів через M+1 станів ємності.
• Складність простору: O(n · M) для повної таблиці, що зводиться до O(M) за допомогою keeping лише попередній рядок, коли tracелектронна зворотна зв'язка не потрібна.

Час виконання псевдополіноміальний: поліноміальний за значенням M, але експоненціальний за бітами, що використовуються для кодування M. Ось чому 0/1 Knapsack залишається NP-складним, навіть якщо динамічне програмування є ефективним на практиці.

Застосування задачі про рюкзак 0/1

• Завантаження вантажів, пакування контейнерів та комплектування на складі під обмеженнями ваги.
• Розподіл бюджету між інвестиційними проектами з фіксованою вартістю та очікуваною прибутковістю.
• Проблеми з розкроєм заготовок у виробництві, які не дозволяють розділити окремі деталі.
• Криптографічні схеми, такі як Меркла-Хеллмана, що базуються на стійкості рюкзака.
• Планування з обмеженими ресурсами в хмарних обчисленнях та розміщення завдань процесора.
• Вибір функцій у машинному навчанні за фіксованого бюджету функцій.

Поширені запитання