Лабораторія 11 Динамічне програмування структур даних та алгоритмів (серія 1AB)

Інструменти користувача

Інструменти сайту

Бічна панель

зміст

1 Лабораторні завдання

2 Динамічне програмування

2.1 Огляд

Динамічне програмування передбачає вирішення проблеми шляхом її розбиття на підзадачі та їх вирішення. На відміну від divide et impera, підпрограми не є несуміжними, а перекриваються.

динамічне

Щоб уникнути перерахунку частин, що перекриваються, рішення приймається, починаючи з найменших підпрограм і використовуючи наш результат, ми обчислюємо негайно більшу підпроблему. Найменші підзадачі називаються унітарними підзадачами, які можуть бути вирішені в постійній складності, наприклад, найбільша послідовність у наборі одного елемента.

2.2 Впровадження

2.3 Типові проблеми, вирішені за допомогою цього алгоритму

2.3.1 Проблема рюкзака

Рішення будується за допомогою динамічного програмування, D [i] [j] = найкраща вартість, отримана для перших i об’єктів, що мають максимальну вагу j.
Відношення рецидивів є таким: D [i] [j] = максимум (D [i-1] [j], D [i-1] [jG [i]] + C [i]), де G [i] = вага об'єкта i, а C [i] = вартість об'єкта.
Ідея полягає в наступному: до поточного рішення ми або взагалі не додаємо об’єкт i, і ми залишаємось за вартість об’єктів i-1, або додаємо об’єкт i, і в цьому випадку ми додаємо його вартість до вартості, отриманої для перших об’єктів i-1, та ваги j-G [i].

2.3.2 Визначення найдовшого висхідного ряду

Приклад: для рядка 24,12,15,8,19 відповідь - рядок 12,15,19.
Ми починаємо з визначення для кожного елемента довжини найдовшого строго зростаючого рядка, який починається з першого елемента і закінчується цим елементом. Ми називаємо це значення найкращим і застосовуємо рекурсивну формулу найкраще i = 1 + max (найкраще j), з jn, тоді ми можемо переписати P (n) = ∏ (Cn, k X k), де k = 0,1,2,… n.

Нехай coef (P, k) = коефіцієнт X k у поліномі P. Тоді ми можемо записати наступні 2 властивості:

Ми можемо вивести зв’язок між коефіцієнтами багаточленів типу P (n), якщо записати P (n + 1) = (X + 1) P (n) = X P (n) + P (n).

Але коефіцієнт коефіцієнта (P (n), k) = C (n, k), тому ми отримали рецидив, який використовує лише одне додавання.

Вправи

3. Лабораторні вправи (Linux)

Для цієї лабораторії ви можете завантажити скелет коду тут. Завантажте архів та розпакуйте його.

Linux

Ви можете використовувати утиліту wget для завантаження та утиліту розпакування для розпакування.