Вот реализация задачи о рюкзаке с использованием динамического программирования на Python:

Метод 1: рекурсивный подход с мемоизацией

def knapsack_recursive_memoization(weights, values, capacity):
    memo = [[-1] * (capacity + 1) for _ in range(len(weights))]
    def knapsack_helper(i, remaining_capacity):
        if i == len(weights) or remaining_capacity == 0:
            return 0
        if memo[i][remaining_capacity] != -1:
            return memo[i][remaining_capacity]
        if weights[i] > remaining_capacity:
            result = knapsack_helper(i + 1, remaining_capacity)
        else:
            include = values[i] + knapsack_helper(i + 1, remaining_capacity - weights[i])
            exclude = knapsack_helper(i + 1, remaining_capacity)
            result = max(include, exclude)
        memo[i][remaining_capacity] = result
        return result
    return knapsack_helper(0, capacity)

Метод 2: подход «снизу вверх» (таблица)

def knapsack_bottom_up(weights, values, capacity):
    n = len(weights)
    dp = [[0] * (capacity + 1) for _ in range(n + 1)]
    for i in range(1, n + 1):
        for w in range(1, capacity + 1):
            if weights[i - 1] <= w:
                dp[i][w] = max(values[i - 1] + dp[i - 1][w - weights[i - 1]], dp[i - 1][w])
            else:
                dp[i][w] = dp[i - 1][w]
    return dp[n][capacity]

Метод 3. Оптимизированное пространство снизу вверх

def knapsack_bottom_up_optimized(weights, values, capacity):
    n = len(weights)
    dp = [0] * (capacity + 1)
    for i in range(1, n + 1):
        for w in range(capacity, 0, -1):
            if weights[i - 1] <= w:
                dp[w] = max(values[i - 1] + dp[w - weights[i - 1]], dp[w])
    return dp[capacity]