Інформатика – Поглиблений рівень

Прочитайте!

Чи доводилося вам раніше у процесі вивчення математики або фізики розбивати складну задачу на декілька дрібніших однотипних задач?
Динамічне програмування — це метод розв’язування задач, що мають певні властивості, шляхом їх розбиття на декілька однотипних підзадач, пов’язаних між собою.

Динамічне програмування — розділ математичного програмування, що вивчає багатокрокові процеси пошуку оптимального вирішення складних завдань.

Застосовується при складанні програм рішення таких задач оптимізації, для яких процес пошуку рішення можна представити у вигляді деякої послідовності кроків, тобто знаходять оптимальне рішення на кожному кроці процесу і таким чином зводять рішення однієї складної задачі до вирішення великого числа значно менш складних. До задач оптимізації відносять задачі пошуку максимальних або мінімальних значень певних функцій. Наприклад, пошуку максимального значення прибутку від інвестування у відповідну галузь за багаторічний період зводиться до послідовного визначення оптимальних капіталовкладень на кожен рік.
Загальним для задач динамічного програмування є те, що змінні в моделі розглядаються не разом, а послідовно, одна за одною, тобто будується така обчислювальна схема, коли замість
одного завдання з багатьма змінними використовують багато завдань з малим числом (зазвичай навіть однієї) змінних у кожній. Це значно скорочує обсяг обчислень. Пояснимо сутність динамічного програмування на найпростішому прикладі.

Приклад 1. Нехай потрібно обчислити суму n чисел: 1+ 2+ 3+ 4 +…+ n. Складність цієї задачі полягає в тому, що необхідно одразу взяти велику кількість чисел і додати їх. Можна спочатку визначити суму першого елемента, тобто просто взяти перший елемент: f (1) =1. Потім до суми можна додати другий елемент: f (2) = f (1)+ 2 = 3. Аналогічно отримуємо: f (3) = f (2)+ 3 = 6, f (n) = f (n −1)+ n.

Приклад 2. Припустимо, що компанія виготовляє процесори (позначимо їх змінною х1), системні плати (х2), монітори (х3) та інші пристрої. Для визначення максимального прибутку
потрібно визначити, яку кількість пристроїв слід виготовити, скільки потрібно мати персоналу тощо. Знайти розв’язок цієї задачі за великої кількості змінних досить складно. Але можна відокремити задачу із змінною x1. Після того як знайдено оптимальний розв’язок для першої
підзадачі, виділяється підзадача з двома змінними x1 і x2, і вона розв’язується за допомогою вже знайденого розв’язку для першої задачі. Потім виділяється підзадача з трьома змінними x1, x2 і x3 і розв’язується за допомогою раніше використаного методу.

Важливо те, що у процесі розв’язування складної задачі не розв’язується заново чергова підзадача, а використовується вже отриманий розв’язок попередньої підзадачі. Наведемо типові задачі, які можна розв’язувати за допомогою динамічного програмування:

• розроблено граф доріг між населеними пунктами певного регіону; потрібно знайти мінімальний маршрут між двома населеними пунктами або маршрут, на який витрачається мінімальна кількість пального;
• корпорація виготовляє процесори, смартфони, монітори та інше обладнання; потрібно визначити оптимальну кількість виготовлення кожного виду пристроїв для отримання максимального прибутку. Розглянемо розв’язування задачі обчислення чисел Фібоначчі на прикладі.

Приклад 3. Складіть програму для обчислення n-го члена послідовності Фібоначчі. (1, 1, 2, 3, 5, 8, … – перші два члени дорівнюють 1, а всі інші – це сума двох попередніх.

• Формат вхідних даних: одне число 0<<100.
• Формат вихідних даних: одне число n-й член послідовності.

Ідея розв’язання обчислення й збереження тільки двох елементів послідовності: у=х+у, х=у-х.

Використавши цю ідею, складіть відповідну програму.

Приклад 4. Нехай є сходи, по яких можна ступати по кожній сходинці або через одну. Скількома способами можна потрапити на i сходинку? На першу сходинку можна потрапити одним способом, на другу — двома, на третю — трьома способами. Кількість способів потрапити на сходинку i дорівнює сумі способів потрапляння на сходинки i −1 і i −2, тобто обчислюється за
допомогою формули f a1 f ai 1 f ai 2 ( ) = ( − )+ ( − ), яка фактично є формулою обчислення чисел
Фібоначчі. Нагадаємо, що числа Фібоначчі, починаючи з третього, отримують шляхом складання двох попередніх чисел, а перше і друге число дорівнюють одиниці: 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89,…
Щоб обчислити деяке число в цій послідовності, спочатку потрібно обчислити третє число, склавши перших два числа, потім четверте, склавши друге і третє числа, і т. д.

Розглянемо програму мовою Python обчислення чисел Фібоначчі на основі рекурентного підходу:

Модифікуйте програму таким чином, щоб обчислювалася тільки сума перших 12 чисел Фібоначчі.

Ще один варіант програми обчислення чисел Фібоначчі:

Виконайте програму для отримання суми перших 15 чисел Фібоначчі. Доведіть, що отримано правильний результат.

Приклад 5. Нехай у касі є монети 1, 2 і 5 копійок, якими слід повернути здачу 7 копійок. Можливі такі варіанти:
1+1+1+1+1+1+1= 7
1+1+1+1+1+ 2 = 7
1+1+1+ 2+ 2 = 7
1+ 2+ 2+ 2 = 7
1+1+5 = 7
2+5 = 7
Усього шість варіантів. Аналіз виконаних дій дозволяє зробити висновок, що процес пошуку кількості варіантів повернення здачі є циклічним і складається із множини вкладених циклів. Кількість таких циклів визначається кількістю типів монет. Кількість виконання кожного вкладеного циклу залежить від суми здачі й номіналу самої монети.

Розглянемо програму визначення кількості варіантів повернення здачі й кількості монет кожного з номіналів 1, 2, 5 і 10:

Визначте, скількома способами можна сплатити суму 60 грн купюрами номіналом 5, 10, 20 і 50 грн.

Приклад 6. Степан збирає речі у відпустку. З собою в літак він може взяти ручну поклажу і багаж. Для ручної поклажі у нього є рюкзак, а для багажу – здоровенна валіза.
За правилами перевезення маса ручної поклажі не повинна перевищувати S кг, а багаж може бути будь-якої маси (за наднормативний багаж Степан готовий доплатити). Зрозуміло, найбільш цінні речі – ноутбук, фотоапарат, документи і т. д. – Степан хоче покласти в ручну поклажу.
Степан розклав усі свої речі в порядку зменшення їх цінності і починає складати найбільш цінні речі в рюкзак. Він діє в такий спосіб – бере найцінніший предмет, і якщо його маса не перевищує S, то кладе його в рюкзак, інакше кладе його до валізи. Потім він бере наступний за цінністю предмет, якщо його можна покласти в рюкзак, тобто якщо його маса разом з масою вже покладених в рюкзак речей не перевищує S, то кладе його в рюкзак, інакше до валізи, і таким же чином процес триває для всіх предметів в порядку спадання їх цінності.
Визначте вагу рюкзака і валізи після того, як Степан складе всі речі.
Розв’язання
В даній задачі необхідно реалізувати принцип, який описаний в умові, а саме: беремо предмет, і якщо його маса не перевищує максимально дозволену масу, то кладемо його в рюкзак, інакше кладемо його до валізи.
Нехай vr – маса рюкзака і vv – маса валізи. Беремо перший предмет з масою r і перевіряємо, якщо vr+r не перевищує s, то збільшуємо vr на r, інакше vv збільшуємо на r.
Розглянемо алгоритм розв’язування задачі:
• ввести значення s та n, присвоїти значення 0 змінним vr і vv;
• за допомогою циклу та команди розгалуження обчислити vr і vv;
• вивести результат.