Написання динамічних алгоритмів

6.1 Основні кроки при розробці динамічних алгоритмів.

Основні кроки при розробці динамічних алгоритмів

1. Визначення підзадач:

Розділіть задачу на менші підзадачі, які можуть бути вирішені незалежно одна від одної. Ці підзадачі мають бути перекриваючими, щоб можна було використовувати результати попередніх обчислень.

2. Ідентифікація станів:

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

3. Формулювання рекурентного співвідношення:

Визначте, як розв'язання задачі для поточного стану залежить від рішень для попередніх станів. Це співвідношення повинно виражати, як можна отримати оптимальне рішення, використовуючи рішення для підзадач.

4. Визначення базових випадків:

Визначте базові випадки, для яких рішення задачі відоме безпосередньо без потреби в подальших обчисленнях.

5. Заповнення таблиці:

Створіть таблицю (зазвичай масив або матриця) для зберігання рішень всіх підзадач. Використовуйте рекурентне співвідношення і базові випадки для заповнення таблиці знизу вгору або зверху вниз.

6. Оптимізація (мемоізація):

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

Часова і простірна складність динамічних алгоритмів

Часова складність:

• Часова складність динамічних алгоритмів зазвичай виражається через кількість підзадач і час, необхідний для обчислення кожної підзадачі.
• У більшості випадків часова складність становить O(n) або O(n^2), де n — розмір вхідних даних.

Простірна складність:

• Простірна складність залежить від кількості станів, які необхідно зберігати.
• У деяких випадках можливе зменшення простірної складності з використанням оптимізацій, таких як скорочення використовуваної пам'яті до O(n) або O(1).

6.2 Задача про рюкзак.

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

Опис задачі про рюкзак

Є рюкзак, який може витримати певну вагу W. Також є n предметів, кожен з яких має певну вагу wt[i] і цінність val[i]. Потрібно визначити, які предмети взяти, щоб максимізувати загальну цінність предметів у рюкзаку, не перевищуючи його вагову місткість.

Види задачі про рюкзак

1. Задача про рюкзак 0/1 (0/1 Knapsack Problem):

Кожен предмет можна або взяти, або не взяти (нельзя брати частково).

2. Задача про дробовий рюкзак (Fractional Knapsack Problem):

Кожен предмет можна розділити і взяти будь-яку його частину.

3. Множинна задача про рюкзак (Multiple Knapsack Problem):

Є декілька рюкзаків з різними ваговими обмеженнями.

Формулювання задачі 0/1 рюкзака в термінах теорії алгоритмів:

Рекурентне співвідношення:

Для кожного предмета i і для кожної можливої ваги w (від 0 до W), оптимальне рішення можна виразити наступним чином:

• Якщо предмет i не включається у рюкзак, то оптимальна цінність дорівнює оптимальній цінності для i − 1 предметів і ваги w.
• Якщо предмет i включається у рюкзак, то оптимальна цінність дорівнює цінності цього предмета плюс оптимальна цінність для i − 1 предметів і ваги w − wt[i].

Часова і простірна складність

Часова складність:

Часова складність цього алгоритму складає O(nW) де n — кількість предметів, а W — місткість рюкзака. Це пов'язано з тим, що необхідно заповнити таблицю розміром n × W.

Простірна складність:

Простірна складність також складає O(nW), адже потрібна таблиця для зберігання проміжних результатів.

Приклади реалізації задачі 0/1 рюкзака

def knapsack(W, wt, val, n):
    # Створюємо таблицю для зберігання проміжних значень
    dp = [[0 for x in range(W + 1)] for x in range(n + 1)]
        
    # Заповнюємо таблицю dp знизу вгору
    for i in range(n + 1):
        for w in range(W + 1):
            if i == 0 or w == 0:
                dp[i][w] = 0
            elif wt[i - 1] <= w:
                dp[i][w] = max(val[i - 1] + dp[i - 1][w - wt[i - 1]], dp[i - 1][w])
            else:
                dp[i][w] = dp[i - 1][w]
        
    return dp[n][W]
        
# Приклад використання
val = [60, 100, 120]
wt = [10, 20, 30]
W = 50
n = len(val)
print(f"Максимальна цінність рюкзака: {knapsack(W, wt, val, n)}")
        

6.3 Задача про розмін монет.

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

Мінімальна кількість монет (Minimum Coin Change Problem):

Знайти мінімальну кількість монет, яка сукупно становить задану суму.

Кількість способів (Number of Ways to Make Change):

Знайти кількість різних способів скласти задану суму з заданого набору монет.

Варіант 1. Мінімальна кількість монет

Постановка задачі

Дано:

• Необмежена кількість монет з певними номіналами.
• Цільова сума S.

Необхідно:

• Знайти мінімальну кількість монет, яка складає суму S.

Рішення з використанням динамічного програмування

Рекурентне співвідношення:

• Нехай dp[i] позначає мінімальну кількість монет, необхідну для складання суми i.
• Для кожної монети c з набору монет, якщо i ≥ c, тоді: dp[i] = min(dp[i], dp[i − c] + 1)

Базові випадки:

• dp[0] = 0 (для суми 0 потрібні 0 монет).

Часова і простірна складність:

• Часова складність: O(n ⋅ S), де n — кількість номіналів монет, S — цільова сума.
• Простірна складність: O(S), оскільки потрібен масив для зберігання мінімальної кількості монет для кожної суми від 0 до S.

Приклад реалізації на Python

def min_coins(coins, S):
    dp = [float('inf')] * (S + 1)
    dp[0] = 0
        
    for i in range(1, S + 1):
        for coin in coins:
            if i >= coin:
                dp[i] = min(dp[i], dp[i - coin] + 1)
        
    return dp[S] if dp[S] != float('inf') else -1
        
# Приклад використання
coins = [1, 2, 5]
S = 11
print(f"Мінімальна кількість монет для суми {S}: {min_coins(coins, S)}")
        
        

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