Лаборатория 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,… н.

Нека coef (P, k) = коефициентът на X k в полинома P. Тогава можем да напишем следните 2 свойства:

Можем да изведем връзка между коефициентите на полиноми от тип P (n), ако напишем P (n + 1) = (X + 1) P (n) = X P (n) + P (n).

Но coef (P (n), k) = C (n, k), така че имаме повторение, което използва само едно добавяне.

Упражнения

3. Лабораторни упражнения (Linux)

За тази лаборатория можете да изтеглите кодовия скелет тук. Изтеглете архива и го разархивирайте.

Linux

Можете да използвате помощната програма wget за изтегляне и помощната програма за разархивиране за разархивиране.