Крипто Devs | Gnezdo Hub

Важно понимать разницу между динамическим программированием и подходом «Разделяй и властвуй». Оба метода дробят задачу, но делают это по-разному. В «Разделяй и властвуй» подзадачи независимы и не перекрываются — каждая решается отдельно и больше не встречается. Классический пример — сортировка слиянием (Merge Sort), где массив делится на независимые половины, которые сортируются сами по себе и никогда не влияют на вычисление друг друга. В динамическом программировании подзадачи обязательно перекрываются: результат одной и той же маленькой задачи требуется при решении нескольких более крупных. Правило выбора подхода простое: если подзадачи перекрываются — используем ДП, если нет — «Разделяй и властвуй».

Классической задачей на ДП является задача о рюкзаке (Knapsack problem). Представь, что у тебя есть рюкзак вместимостью W и набор из n предметов, каждый из которых имеет свой вес w[i] и ценность v[i]. Цель — набрать предметы так, чтобы их суммарная ценность была максимальной, а суммарный вес не превысил W. Например, при вместимости рюкзака W = 7 и предметах с весами и ценностями (1, 1), (3, 4), (4, 5), (5, 7) лучшим выбором будут предметы 2 и 3 (вес 3+4=7, ценность 4+5=9). Почему это задача ДП? Потому что при решении вопроса «брать или не брать предмет i» мы приходим к подзадачам, которые будут переиспользоваться. Если мы берем предмет, нам нужно решить ту же задачу для оставшихся предметов с вместимостью W - w[i]. Если не берем — для оставшихся предметов с той же вместимостью W. Эти подзадачи постоянно повторяются в разных комбинациях. Решается задача методом табуляции. Мы создаем таблицу dp[i][w], где значение в ячейке — это максимальная ценность, которую можно получить, используя первые i предметов при вместимости рюкзака w. Логика заполнения таблицы такова: если вес текущего предмета больше текущей вместимости w, он просто не помещается, и мы берем значение сверху (без этого предмета): dp[i][w] = dp[i-1][w]. Если же предмет помещается, у нас есть два варианта: не брать его (dp[i-1][w]) или взять, добавив его ценность к оптимальному решению для оставшегося места (dp[i-1][w - w_i] + v_i). Выбираем максимум.

def knapsack(weights, values, W):
    """
    Решение задачи о рюкзаке методом ДП (табуляция).
    
    weights — список весов предметов
    values  — список ценностей предметов
    W       — вместимость рюкзака
    """
    n = len(weights)
    dp = [[0] * (W + 1) for _ in range(n + 1)]

    for i in range(1, n + 1):
        w_i = weights[i - 1]
        v_i = values[i - 1]

        for w in range(W + 1):
            dp[i][w] = dp[i - 1][w]
            if w_i <= w:
                dp[i][w] = max(dp[i][w], dp[i - 1][w - w_i] + v_i)

    return dp[n][W]


weights = [1, 3, 4, 5]
values  = [1, 4, 5, 7]
W = 7

print(knapsack(weights, values, W))  # 9

Временная сложность этого алгоритма составляет O(n × W), что называется псевдополиномиальной, так как зависит не только от количества предметов, но и от значения вместимости W.

Итак, резюмируя, динамическое программирование — это мощный инструмент, который подходит для задач, обладающих двумя ключевыми свойствами: оптимальной подструктурой (решение большой задачи строится из решений подзадач) и перекрывающимися подзадачами (одни и те же подзадачи решаются многократно). В зависимости от контекста мы можем использовать либо нисходящее рекурсивное решение с кэшированием (мемоизация), либо восходящее итеративное заполнение таблицы (табуляция). Это принципиально отличает ДП от подхода «Разделяй и властвуй», где подзадачи всегда независимы.

#algorithm

📟 Прилетело из @solidityset

40 views09:12