Файлы и большие данные · тема 5 из 8
Отбор под ограничение
Сортировка и жадный выбор · ЕГЭ 26
Одна идея — один пример
Если нужно взять максимум предметов положительного размера при ограничении суммы, начинай с самых маленьких. Это работает для этой цели, но не для любой оптимизации.
print(sorted([8, 2, 5]))Теперь решаем самостоятельно
После сортировки первый не поместившийся предмет означает, что следующие тоже не поместятся. Для максимума ценности этот алгоритм может быть неверен.
Первая строка — вместимость s ≥ 0. Вторая — положительные целые размеры предметов. Найди максимальное количество предметов с общей суммой не больше s.
Пример входных данных и результата
Ввод:
10 8 2 5 3
Вывод:
3
Черновик и файл программы
Черновик сохраняется в этом браузере. Ctrl/⌘ + S — сохранить.
Результаты проверки
Напиши решение и нажми «Проверить код». Данные каждого теста подаются автоматически.
Нужна подсказка?
Сначала сортировка, затем вычитание размера из остатка вместимости.
На чём легко ошибиться
Условие «не больше» включает точное заполнение.
Разобрать один из способов решения
Сначала попробуй написать код сам. Сравни алгоритм, затем закрой разбор и воспроизведи решение без подсказки.
s = int(input())
a = sorted(map(int, input().split()))
count = 0
for x in a:
if x > s: break
s -= x
count += 1
print(count)Тесты проверяют результат на учебных примерах, но не доказывают правильность для любого входа. Объясни каждую строку и предложи собственный тест.
Перед следующей темой
Назови входные данные, результат, основной шаг алгоритма и граничный случай. Если использовал разбор, напиши решение заново. Для свободных экспериментов открой Python онлайн.
Все темы этого курса
Программа подготовлена по темам банка «Академии С». Официальные документы: ФИПИ. Справочник языка: Python. Не все экзаменационные задачи нужно решать программой: например, работа в таблицах требует освоения табличного редактора.