Динамическое программирование: Мемоизация, 0-1 Рюкзак и Перемножение матриц

Полный разбор ДП: перекрывающиеся подзадачи, оптимальная подструктура, Top-Down vs Bottom-Up, задача о рюкзаке (0-1 Knapsack) и задача о расстановке скобок при перемножении цепочки матриц (Matrix Chain Multiplication).

Исходная заготовка: полнота объяснения и примеров ожидает редакторской проверки.

Динамическое программирование: предварительные знания, план уроков и практика →

Фундамент динамического программирования

ДП применяется, когда задача обладает:

Оптимальной подструктурой: Оптимум выражается через оптимумы меньших подзадач;

Перекрывающимися подзадачами (Overlapping Subproblems): Одно и то же состояние вычисляется многократно.

1. Дискретная задача о 0-1 рюкзаке

Даны $N$ предметов с весами $w_i$ и стоимостями $v_i$ . Вместимость $W$ .

dp[i][w] = \max(dp[i-1][w], dp[i-1][w - w_i] + v_i)

cpp

int knapsack(int W, const vector<int>& wt, const vector<int>& val) {
    int n = wt.size();
    vector<int> dp(W + 1, 0);
    for (int i = 0; i < n; ++i) {
        for (int w = W; w >= wt[i]; --w) {
            dp[w] = max(dp[w], dp[w - wt[i]] + val[i]);
        }
    }
    return dp[W];
}

2. Перемножение цепочки матриц (Matrix Chain Multiplication)

Дана цепочка матриц $A_1 A_2 \dots A_n$ , где $A_i$ имеет размер $p_{i-1} \times p_i$ . Найти порядок расстановки скобок с минимальным числом скалярных умножений.

m[i, j] = \min_{i \le k < j} \{ m[i, k] + m[k+1, j] + p_{i-1} p_k p_j \}

Сложность: $O(N^3)$ времени и $O(N^2)$ памяти.

Что дальше?

Закрепите материал задачей: Повторить число.

Изучено — к практике →

Отметка сохранится в этом браузере. Её можно отменить или снять кнопкой «Изучено».