Как решать олимпиадные задачи на языке Python
Основные подходы к решению олимпиадных задач на Python
Олимпиадные задачи по программированию часто требуют нестандартных решений и знания классических алгоритмов. Рассмотрим одну из популярных задач – задачу о рюкзаке 0/1 (Knapsack). Она служит хорошей иллюстрацией применения динамического программирования, рекурсии и оптимизации.
Как найти максимальную стоимость предметов, не превышая вместимость рюкзака?
Эффективное решение строится на динамическом программировании. Создается таблица dp размером (n+1) x (capacity+1), где dp[i][w] – максимальная стоимость, которую можно получить из первых i предметов при весе не более w. Заполнение таблицы происходит по правилу: если вес предмета меньше или равен текущей вместимости, то выбирается максимум между стоимостью без этого предмета и стоимостью с ним.
def knapsack_01(weights, values, capacity):
n = len(weights)
dp = [[0] * (capacity + 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(1, capacity + 1):
if w_i <= w:
dp[i][w] = max(dp[i-1][w], dp[i-1][w - w_i] + v_i)
else:
dp[i][w] = dp[i-1][w]
return dp[n][capacity]
weights = [2, 3, 4, 5]
values = [3, 4, 5, 6]
capacity = 5
print(knapsack_01(weights, values, capacity))яндекс задания python (задания от яндекса по python)
7
Python разработчик тестовые задания (примеры тестовых заданий python)
В таблице dp строки соответствуют предметам, столбцы – весу. Значение в правой нижней ячейке и будет ответом. Этот метод гарантирует оптимальность за O(n*capacity).
Как реализовать рекурсивное решение с запоминанием результатов?
Рекурсия с мемоизацией (lru_cache или собственный словарь) позволяет избежать построения полной таблицы, если многие состояния не достигаются. Однако в худшем случае сложность та же, но добавляются накладные расходы на рекурсию.
from functools import lru_cache
def knapsack_rec(weights, values, capacity):
@lru_cache(maxsize=None)
def dfs(i, w):
if i == 0 or w == 0:
return 0
if weights[i-1] > w:
return dfs(i-1, w)
return max(dfs(i-1, w), dfs(i-1, w - weights[i-1]) + values[i-1])
return dfs(len(weights), capacity)
print(knapsack_rec([2,3,4,5], [3,4,5,6], 5))программирование python задание 18 (задание 18 по программированию на python)
7
Важно: при больших capacity может возникнуть переполнение стека рекурсии. В таких случаях лучше использовать итеративное DP.
Типичные ошибки и их устранение
Ошибка 1: Неверный порядок циклов при заполнении таблицы. Внешний цикл должен идти по предметам, внутренний – по весу. Если поменять местами, то предмет может быть использован несколько раз (эффект неограниченного рюкзака).
Ошибка 2: Рекурсия без мемоизации – время экспоненциально растет с числом предметов. Решение: добавить кэш или перейти на DP.
Ошибка 3: Игнорирование ограничений по памяти для двумерного массива при большом capacity. Выход: использовать одномерный массив с обновлением справа налево (для 0/1 рюкзака).
Дополнительные примеры олимпиадных задач
Задача о рюкзаке с неограниченным количеством предметов
В этом варианте каждый предмет можно брать любое число раз. Решение через одномерное DP, где цикл по весу идет слева направо.
def unbounded_knapsack(weights, values, capacity):
dp = [0] * (capacity + 1)
for w in range(1, capacity + 1):
for i in range(len(weights)):
if weights[i] <= w:
dp[w] = max(dp[w], dp[w - weights[i]] + values[i])
return dp[capacity]
weights = [2, 3, 4]
values = [3, 4, 5]
capacity = 7
print(unbounded_knapsack(weights, values, capacity))10
Здесь используется предмет весом 4 (стоимость 5) и предмет весом 3 (стоимость 4) – общая стоимость 9, но можно взять два предмета по 3 (стоимость 8) или один 4 + один 3 = 9, а лучше взять два по 2 (6) + один 3 (4) = 10. Ответ верен.
Задача о разделении множества на два подмножества с равной суммой
Это частный случай рюкзака: нужно определить, можно ли набрать сумму, равную половине общей суммы, используя каждый предмет не более одного раза.
def can_partition(nums):
total = sum(nums)
if total % 2 != 0:
return False
target = total // 2
dp = [False] * (target + 1)
dp[0] = True
for num in nums:
for w in range(target, num - 1, -1):
if dp[w - num]:
dp[w] = True
return dp[target]
print(can_partition([1, 5, 11, 5])) # [1,5,5] и [11] -> True
print(can_partition([1, 2, 3, 5])) # FalseTrue False
Задача о наибольшей возрастающей подпоследовательности (LIS)
Классическая задача на динамическое программирование. Найти длину самой длинной строго возрастающей подпоследовательности.
def length_of_lis(nums):
if not nums:
return 0
dp = [1] * len(nums)
for i in range(len(nums)):
for j in range(i):
if nums[j] < nums[i]:
dp[i] = max(dp[i], dp[j] + 1)
return max(dp)
print(length_of_lis([10, 9, 2, 5, 3, 7, 101, 18]))4
Подпоследовательность: [2,5,7,101] или [2,3,7,101] – длина 4.