Задача о рюкзаке 0–1 — это классическая задача оптимизации в информатике. Он предполагает выбор предметов из набора, каждый из которых имеет определенный вес и ценность, чтобы максимизировать общую ценность, сохраняя при этом общий вес в заданных пределах.

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

def knapsack(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]
# Example usage
weights = [2, 3, 4, 5]
values = [3, 4, 5, 6]
capacity = 8
max_value = knapsack(weights, values, capacity)
print("Maximum value:", max_value)

В этой реализации список weightsпредставляет веса элементов, список valuesпредставляет значения элементов, а емкостьпредставляет собой максимальный вес, который может выдержать рюкзак.

В реализации используется двумерный массив dpдля хранения максимального значения, которое может быть достигнуто при каждой дополнительной мощности между 0 и заданной мощностью. Он перебирает каждый элемент и каждую дополнительную мощность, решая, лучше ли включить текущий элемент или исключить его, исходя из веса и ценности.

Окончательное значение, хранящееся в dp[n][capacity], представляет собой максимальное значение, которое может быть достигнуто с использованием заданных весов, значений и емкости.

Некоторые другие методы решения задачи о рюкзаке 0-1 включают рекурсивный поиск с возвратом, мемоизацию и алгоритмы ветвей и границ. Каждый метод имеет свои преимущества и недостатки с точки зрения временной и пространственной сложности.