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

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)}")
        
        

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