Как решить эту задачу(ЕГЭ информатика 2021)?

Question

[g1shy \(#_#)/]

Задача:
Системный администратор раз в неделю создаёт архив пользовательских файлов. Однако объём диска, куда он помещает архив, может быть меньше, чем суммарный объём архивируемых файлов. Известно, какой объём занимает файл каждого пользователя.

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

Входные данные:
В первой строке входного файла находятся два числа: S — размер свободного места на диске (натуральное число, не превышающее 10 000) и N — количество пользователей (натуральное число, не превышающее 2000). В следующих N строках находятся значения объёмов файлов каждого пользователя (все числа натуральные, не превышающие 100), каждое в отдельной строке.

Запишите в ответе два числа: сначала наибольшее число пользователей, чьи файлы могут быть помещены в архив, затем максимальный размер имеющегося файла, который может быть сохранён в архиве, при условии, что сохранены файлы максимально возможного числа пользователей.

Пример входного файла:
100 4
80
30
50
40
При таких исходных данных можно сохранить файлы максимум двух пользователей. Возможные объёмы этих двух файлов 30 и 40, 30 и 50 или 40 и 50. Наибольший объём файла из перечисленных пар — 50, поэтому ответ для приведённого примера:
2 50

Всё, на что у меня хватило сил, это найти максимальное число пользователей:

spoiler

и то неправильно

f = open("zadanie26_var_1.txt")
s = list(f)
k = 0
for i in range(int(s[1]), len(s)):
    if s[i] + s[i+1] <= s[0]:
        k+=1
        print(k)

Хелпаните, ребят! Буду рад любой подсказке, которая поможет сдвинуть процесс решения с одного места.

Answer 1

[Сергей П]

Тут задачки постить запрещено, но какой-то код вы предложили, хотя и неправильный, поэтому заслужили подсказку. Вам бы я осоветовал не код сперва писать, а порассуждать о том как собираетесь решать задачу. Придумайте алгоритм сначала на русском языке в свободной форме. У вас нет никакого опыта, поэтому язык программирования вас слишком сильно отвлекает от сути задачи.

Есть такая классическая задача "упаковка рюкзака". Там даны неделимые предметы и их массы. У рюкзака есть максимально допустимая масса. Все предметы в рюкзак не влезут, но нужно нужно пдобрать такой набор, чтобы нагрузить рбюкзак максимально. Эта задача вычислительно сложная при большом числе предметов. Она решается полным перебором.

Ваша же задача гораздо проще. Вам нужно положить в такой рюкзак как можно больше предметов из имеющихся, чтобы не превысить максмальную массу (в вашем слуае объём бэкап-диска).
Вот у вас есть большой набор разных гирек, и нужно максимальное число гирек разместить на чаше весов, чтобы не превысить какой-то вес. Как вы будете выбирать гирьки?

Вот такая вот вам подсказка. Думайте, решайте, задавайте конкретные вопросы и вам дадут еще подсказок. Но готового решения вам здесь, надеюсь, не дадут. Нам нужна достойная смена, а не двоичники, за которых дяди задачки решают.

Давайте я вам ещё рефакторинг вашего кода сделаю. Это не сделает его правильным, но он станет лучше.

with open("zadanie26_var_1.txt") as f:  # Так открытый файл будет закрыт после считывания
    # Так вы считаете первые два числа в отдельные переменные:
    total_volume, users_count = map(int, f.readline().strip().split())
    # А так считаете остальные строки в список и нечаянные пустые строки вас не смутят:
    user_sizes = [int(line.strip()) for line in f if line]  

# Хорошо бы вынести логику решения в отдельную функцию:
def solve(s, n, lst):
    # Вот так можно сделать проверки корректности (ну чисто для себя) входных данных:
    assert s <= 10000, 'Invalid total volume'
    assert len(lst) == n, 'Users count is not valid.'
    assert n <= 2000, 'Wrong users count.'
    assert all(0 < x <= 100 for x in lst), 'Invalid user size.'

    # Вот здесь вот вы сделаете нужные вычисления ;)
    backup_users_count = ...
    max_backup_file_size = ...

    return backup_users_count, max_backup_file_size

# Ну а вызвать функцию и напечатать ее результат вы тоже сумеете, правда?

Comments

[g1shy \(#_#)/]

Сергей Паньков, Спасибо за совет! Что ж, буду думать

[Сергей П]

g1shy \(#_#)/, Я там вам отрефакторил код немножко. Но решать а вас я ничего не стану=)

[IlyaK1]

Подсказка и вправду помогла), но я совершенно не могу понять, как получить второй ответ (максимальный размер имеющегося файла, который может быть сохранён в архиве, при условии, что сохранены файлы максимально возможного числа пользователей). Был бы рад, если бы вы ещё раз подсказали)

[IlyaK1]

Хотя... есть у меня, конечно, идея одна. (перейдём от файлов и диска к рюкзаку и предметам) Заключается она в том, что нужно собрать в рюкзак самые лёгкие предметы (сколько вместится) (так мы, кстати, получим ответ на первый вопрос), а потом уберём самый последний предмет (самый тяжёлый). Далее мы считаем, сколько места осталось в рюкзаке, и смотрим, какие предметы остались (не в рюкзаке). Вес самого тяжёлого предмета, который сможет поместиться в оставшееся место, и будет ответом на второй вопрос.
Как думаете, верная догадка? Заранее спасибо)

Answer 2

[milssky]

Так или иначе, эти задачи связаны с сортировками.