0/1 Виправлення проблеми з рюкзаком за допомогою прикладу динамічного програмування
Сара Чен
Що таке проблема ранця?
Проблема з ранцем Алгоритм є дуже корисною проблемою в комбінаториці. У супермаркеті є n пакетів (n ≤ 100), пакунок i має вагу W[i] ≤ 100 і значення V[i] ≤ 100. Злодій проникає в супермаркет, злодій не може нести вагу, що перевищує M (M ≤ 100). ). Проблема, яку потрібно вирішити, полягає в тому, які пакунки забере злодій, щоб отримати найбільшу вартість?
Вхідний сигнал:
- Максимальна вага М і кількість упаковок n.
- Масив ваги W[i] і відповідного значення V[i].
вихід:
- Максимальна вартість і відповідна вага в місткості.
- Які пакети забере злодій.
Алгоритм ранця можна далі розділити на два типи:
- Задача ранця 0/1 з використанням динамічного програмування. У цьому типі алгоритму Knapsack кожен пакет можна взяти або не взяти. Крім того, злодій не може взяти дрібну кількість вилученого пакунка або забрати пакунок більше одного разу. Цей тип можна вирішити за допомогою підходу динамічного програмування.
- Алгоритм дробової задачі Ранець. Цей тип можна вирішити за допомогою Greedy Strategy.
Як вирішити проблему ранця за допомогою динамічного програмування з прикладом
У стратегії «розділяй і володарюй» ви розділяєте проблему, яку потрібно вирішити, на підпроблеми. Підпроблеми далі поділяються на менші підпроблеми. Це завдання триватиме, доки ви не отримаєте підпроблеми, які можна легко вирішити. Однак у процесі такого поділу ви можете неодноразово зіткнутися з однією і тією ж проблемою.
Основна ідея динамічного програмування Knapsack полягає у використанні таблиці для зберігання рішень розв’язаних підзадач. Якщо ви знову зіткнетеся з підпроблемою, вам просто потрібно взяти рішення в таблиці, не вирішуючи її знову. Тому алгоритми, розроблені за допомогою динамічного програмування, дуже ефективні.
Для вирішення задачі методом динамічного програмування необхідно виконати наступні завдання:
- Знайти рішення найменших підзадач.
- Знайдіть формулу (або правило) для побудови розв’язку підзадачі через розв’язки навіть найменших підзадач.
- Створіть таблицю, яка зберігає розв’язки підзадач. Потім за знайденою формулою розрахувати розв’язок підзадачі та зберегти в таблиці.
- З розв’язаних підзадач ви знайдете розв’язок вихідної задачі.
Проаналізуйте проблему ранця 0/1
Аналізуючи задачу 0/1 Рюкзак за допомогою динамічного програмування, можна знайти деякі помітні моменти. Цінність алгоритму рюкзака залежить від двох факторів:
- Скільки пакетів розглядається
- Залишок ваги, який може вмістити рюкзак.
Отже, у вас є дві змінні величини.
З динамічним програмуванням ви маєте корисну інформацію:
- цільова функція буде залежати від двох змінних величин
- таблиця опцій буде 2-вимірною таблицею.
Якщо виклик B[i][j] є максимально можливим значенням шляхом вибору в пакетах {1, 2, …, i} з обмеженням ваги j.
- Максимальне значення при виборі в n упаковках з обмеженням ваги M становить B[n][M]. Іншими словами: коли є i пакунків для вибору, B[i][j] є оптимальною вагою, коли максимальна вага рюкзака дорівнює j.
- Оптимальна вага завжди менша або дорівнює максимальній вазі: B[i][j] ≤ j.
Наприклад: B[4][10] = 8. Це означає, що в оптимальному випадку загальна вага вибраних пакетів дорівнює 8, коли є 4 перших пакети на вибір (з 1-го по 4-й пакет) і максимальна вага рюкзака становить 10. Необов'язково, щоб були обрані всі 4 предмети.
Формула для обчислення B[i][j]
Вхід, який ви визначаєте:
- W[i], V[i], у свою чергу, є вагою та вартістю упаковки i, в якій i
![Формула для обчислення B[i][j]](data:image/svg+xml,%3Csvg%20xmlns='http://www.w3.org/2000/svg'%20viewBox='0%200%2016%2023'%3E%3C/svg%3E)
{1, …, n}. - М — максимальна вага, яку може нести рюкзак.
![Формула для обчислення B[i][j]](https://www.guru99.com/images/1/043019_0611_KnapsackPro4.png){kind=small}
{1, …, n}.У випадку простого вибору лише 1 упаковки. Ви обчислюєте B[1][j] для кожного j: це означає, що максимальна вага рюкзака ≥ ваги 1-го пакунка
B[1][j] = W[1]
З обмеженням ваги j оптимальний вибір серед пакетів {1, 2, …, i – 1, i} для найбільшого значення матиме дві можливості:
- Якщо пакет i не вибрано, B[i][j] є максимально можливим значенням, вибраним серед пакетів {1, 2, …, i – 1} з обмеженням ваги j. Ти маєш:
B[i][j] = B[i – 1][j]
- Якщо вибрано пакет i (звичайно, розглядайте лише цей випадок, коли W[i] ≤ j), тоді B[i][j] дорівнює значенню V[i] пакета i плюс максимальне значення можна отримати, вибравши серед пакети {1, 2, …, i – 1} з обмеженням ваги (j – W[i]). Тобто з точки зору вартості, яку ви маєте:
B[i][j] = V[i] + B[i – 1][j – W[i]]
Завдяки створенню B[i][j], яке є максимально можливим значенням, B[i][j] буде максимальним із 2 вищезазначених значень.
Основи динамічного програмування
Отже, ви повинні подумати, чи краще вибрати пакет i чи ні. Звідти ви отримаєте рекурсивну формулу наступним чином:
B[i][j]= max(B[i – 1][j], V[i]+B[i – 1][j – W[i]]
Легко побачити, що B[0][j] = максимальне можливе значення, вибравши з 0 package = 0.
Розрахувати таблицю параметрів
Ви створюєте таблицю параметрів на основі наведеної вище рекурсивної формули. Щоб перевірити, чи результати правильні (якщо ні, ви перебудовуєте цільову функцію B[i][j]). Через створення цільової функції B[i][j] і таблиці параметрів ви орієнтуєте трасування.
Таблиця варіантів B містить n + 1 рядків, M + 1 стовпців,
- По-перше, заповнений основою динамічного програмування: рядок 0 містить усі нулі.
- Використовуючи рекурсивні формули, використовуйте рядок 0 для обчислення рядка 1, використовуйте рядок 1 для обчислення рядка 2 тощо... доки не буде обчислено всі рядки.
Трасування
Під час обчислення таблиці опцій вас цікавить B[n][M], яке є максимальним значенням, отриманим при виборі в усіх n упаковках з обмеженням ваги M.
- If B[n][M] = B[n – 1][M] тоді пакет n не вибрано, ви відстежуєте B[n – 1][M].
- If B[n][M] ≠ B[n – 1][M], ви помітили, що оптимальний вибір має пакет n і трасу B[n – 1][M – W[n]].
Продовжуйте відстежувати, поки не досягнете рядка 0 таблиці параметрів.
Алгоритм пошуку таблиці параметрів для пошуку вибраних пакетів
Примітка. Якщо B[i][j] = B[i – 1][j], пакет i не вибрано. B[n][W] – оптимальна загальна вартість упаковки, що поміщається в рюкзак.
Кроки для відстеження:
- крок 1: Починаючи з i = n, j = M.
- крок 2: Подивіться в стовпець j, вгору знизу, ви знайдете рядок i такий, що B[i][j] > B[i – 1][j]. Позначити вибраний пакет i: Виберіть [i] = true;
- крок 3: j = B[i][j] – W[i]. Якщо j > 0, перейдіть до кроку 2, інакше перейдіть до кроку 4
- крок 4: на основі таблиці опцій для друку вибраних пакетів.
Java код
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: ");
while (n != 0) {
if (B[n][M] != B[n - 1][M]) {
System.out.println("\tPackage " + n + " with W = " + W[n - 1] + " and Value = " + V[n - 1]);
M = M - W[n-1];
}
n--;
}
}
Пояснення коду Knapsack:
- Створіть таблицю B[][]. Встановіть значення за умовчанням для кожної комірки – 0.
- Побудуйте таблицю B[][] у спосіб «знизу вгору». Розрахувати таблицю варіантів з формулою пошуку.
- Обчисліть B[i][j]. Якщо ви не вибрали пакет i.
- Потім оцініть: якщо ви виберете пакет i, це буде більш вигідно, ніж скинути B[i][j].
- Простежте таблицю від рядка n до рядка 0.
- Якщо ви обираєте пакет n. Після вибору пакета n можна додати лише вагу M – W[n – 1].
У цьому підручнику ви маєте два приклади. Ось код Java для запуску вищевказаної програми з двома прикладами:
public void run() {
/*
* Pack and Weight - Value
*/
//int W[] = new int[]{3, 4, 5, 9, 4};
int W[] = new int[]{12, 2, 1, 1, 4};
//int V[] = new int[]{3, 4, 4, 10, 4};
int V[] = new int[]{4, 2, 1, 2, 10};
/*
* Max Weight
*/
//int M = 11;
int M = 15;
int n = V.length;
/*
* Run the algorithm
*/
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