Динамическое программирование – это метод решения оптимизационных задач, основанный на разбиении исходной задачи на более мелкие подзадачи и использовании ранее найденных решений для поиска оптимального решения всей задачи. Задачи динамического программирования решаются с помощью установления рекурсивных отношений между решением исходной задачи и решениями её подзадач, что позволяет использовать значения начальных подзадач в последующих вычислениях. Результат вычислений сохраняется в таблице, к которой можно обращаться без повторных вычислений значений, ускоряя процесс нахождения оптимального решения. Ниже рассмотрим пример решения задачи о рюкзаке методом динамического программирования на языке Python. Задача о рюкзаке: имеется набор предметов, каждый из которых характеризуется своей весом и стоимостью. Требуется уложить в рюкзак максимальную стоимость предметов при условии, что суммарный вес не превышает заданной вместимости рюкзака. Решением задачи о рюкзаке является максимальная возможная стоимость предметов, которые можно уложить в рюкзак. Рассмотрим алгоритм решения задачи о рюкзаке методом динамического программирования на языке Python. Создадим таблицу размером n x W, где n – количество предметов, а W – вместимость рюкзака. Для заполнения таблицы, будем идти по строкам и заполнять каждый столбец. Значение ячейки [i,j] будет равно максимальной стоимости предметов, которую можно уложить в рюкзак вместимостью j из i первых предметов. Пример кода на Python для решения задачи о рюкзаке:

python
def knapsack(n, W, wt, val):
    #создаем таблицу размером (n+1) x (W+1)
    K = [[0 for x in range(W+1)] for x in range(n+1)]
 
    #заполняем таблицу
    for i in range(n+1):
        for j in range(W+1):
            if i==0 or j==0:
                K[i][j] = 0
            elif wt[i-1] <= j:
                K[i][j] = max(val[i-1] + K[i-1][j-wt[i-1]],  K[i-1][j])
            else:
                K[i][j] = K[i-1][j]
 
    return K[n][W]

#пример использования
n = 3 #количество предметов
W = 50 #вместимость рюкзака
val = [60, 100, 120] #стоимость предметов
wt = [10, 20, 30] #вес предметов
print(knapsack(n, W, wt, val)) #вывод максимальной стоимости предметов, которые можно уложить в рюкзак

В данном примере решение задачи о рюкзаке методом динамического программирования основывается на таблице K, которая заполняется по формуле K[i][j] = max(val[i-1] + K[i-1][j-wt[i-1]], K[i-1][j]) или K[i][j] = K[i-1][j], в зависимости от условия wt[i-1] <= j. Таким образом, пример решения задачи о рюкзаке на языке Python показывает, что метод динамического программирования позволяет эффективно и правильно решать сложные оптимизационные задачи за приемлемое время с помощью рекурсивных отношений между решениями исходной и подзадач и таблицы, хранящей результаты вычислений.