Задание EGEINF70B483: Сортировка, отбор и моделирование

Решение.

Сохраним приложенный текстовый файл под именем data.txt. Первая строка задаёт параметры задачи; её нельзя считать обычной записью данных. В программе нумерация элементов списка начинается с нуля, а номера из условия сохраняются без сдвига.

Грузоподъёмность S = 99990, количество контейнеров N = 9999. Ограничение относится к суммарной массе; число грузовых мест не мешает выбору. Сначала нужно максимальное количество, и только среди таких наборов — наибольший вес одного контейнера.

Сортируем массы по возрастанию и берём наибольший начальный отрезок, сумма которого не превышает S. Пусть его длина k. Любой набор k + 1 контейнеров весит не меньше суммы k + 1 самых лёгких, которая уже превышает S. Значит, больше k перевезти нельзя.

Для второго критерия оставим k − 1 самых лёгких контейнеров. Их сумма минимальна, поэтому для последнего контейнера остаётся максимально возможный запас R = S − сумма первых k − 1. Среди остальных выбираем наибольшую массу не больше R. Нельзя выбирать уже занятый экземпляр повторно.

Любой другой набор из k контейнеров с самым тяжёлым весом w содержит ещё k − 1 контейнеров, чья сумма не меньше нашей. Поэтому w ≤ R, а выбранный максимум не меньше w. Это доказывает второй критерий. Сортировка O(N log N), остальные действия O(N), память O(N).

Полная программа на Python:

with open("data.txt", encoding="utf-8-sig") as f:
    capacity, n = map(int, f.readline().split())
    weights = sorted(int(f.readline()) for _ in range(n))
total = 0
count = 0
for weight in weights:
    if total + weight > capacity:
        break
    total += weight
    count += 1
if count == 0:
    print(0, 0)
else:
    prefix = sum(weights[:count - 1])
    limit = capacity - prefix
    heaviest = max(w for w in weights[count - 1:] if w <= limit)
    print(count, heaviest)

Проверка результата.

Набор из 1612 контейнеров с максимальной массой одного 90 весит 99957 ≤ 99990. Сумма 1613 самых лёгких контейнеров равна 99997 > 99990, что исключает увеличение количества. В достигающем ответ наборе каждый исходный контейнер выбран не более одного раза.

Ответ: 1612 90.