1Авторская задача
В первой строке указаны грузоподъёмность машины и число грузов. Далее по строке на груз дана положительная целая масса. Каждый груз можно взять один раз. Найдите максимальное число грузов и наибольшую массу отдельного груза среди наборов такого размера. Грузоподъёмность можно исчерпать ровно.
Решение
Число грузов максимизируют самые лёгкие. После фиксации k оставляем k−1 самых лёгких и ищем самый тяжёлый подходящий из оставшихся. Любой другой набор из k−1 грузов весит не меньше этого префикса, поэтому замена покрывает все возможные максимальные массы.
from pathlib import Path
lines = Path("26-gruzy.txt").read_text().splitlines()
limit, n = map(int, lines[0].split())
a = sorted(map(int, lines[1:]))
assert len(a) == n
total = count = 0
for value in a:
if total + value > limit:
break
total += value
count += 1
prefix = sum(a[:count-1])
max_weight = max(value for value in a[count-1:] if prefix + value <= limit)
print(count, max_weight)