Функция точно решает задачу «подобрать грузы как можно тяжелее, но не тяжелее лимита», перебирая все подмножества из n грузов. Определите время выполнения.
Перебор всех подмножеств
Код
from itertools import combinations
def best_load(weights: list[int], limit: int) -> int:
best = 0
for size in range(len(weights) + 1):
for subset in combinations(weights, size):
total = sum(subset)
if best < total <= limit:
best = total
return bestКакое время выполнения?
Ответ: O(2ⁿ · n)
Подмножеств 2ⁿ (каждый предмет либо берём, либо нет), и для каждого сумма считается за O(n) — итого O(2ⁿ · n). Уже при n = 40 это больше триллиона шагов. Поэтому для NP-полных задач вроде этой на практике используют приближённые (например, жадные) алгоритмы. O(n!) — это перебор всех перестановок, как в задаче о коммивояжёре; он растёт ещё быстрее.
- Подсказка 1
Сколько всего подмножеств у множества из n элементов? Каждый элемент либо входит, либо нет.
- Подсказка 2
Для каждого подмножества код ещё и суммирует его элементы — сколько это стоит в худшем случае?