Жадный выбор

На диске свободно 60, а размеры файлов — 8, 12, 15, 19, 22 и 34. Как сохранить как можно больше файлов?

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

Получили четыре файла. Почему пять сохранить невозможно? Потому что пять самых маленьких файлов имеют сумму 8 + 12 + 15 + 19 + 22 = 76 > 60, а любые другие пять файлов имеют не меньшую сумму. Это видно, если выписать оба набора по возрастанию друг под другом: i-й файл любого набора не меньше i-го самого маленького. На рисунке то же сравнение для наборов из четырёх файлов.

Код повторяет ручные действия. Пройди его по шагам:

sizes = [19, 8, 34, 12, 22, 15]capacity = 60sizes.sort()used = 0count = 0for size in sizes:    if used + size > capacity:        break    used += size    count += 1print(count, used)

Здесь used — уже занятый объём, count — количество выбранных файлов. Проверяем возможность добавления до изменения суммы.

Почему разрешён break? Потому что список отсортирован по возрастанию: если текущий файл не помещается, следующие ещё крупнее. Без сортировки такой выход из цикла мог бы пропустить маленький файл в конце списка: для [19, 8, 34, ...] цикл остановился бы на 34, не дойдя до 12 и 15.

Брать самое маленькое — это и есть «жадный алгоритм»? И всегда ли он прав?

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

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

Одного ощущения «так выгоднее» мало. Объясняют двумя способами. Первый: выбранный объект оставляет не меньше возможностей. Файл поменьше оставляет больше места для следующих. Второй: можно заменить чужой выбор нашим и не ухудшить результат. Если в некотором лучшем наборе взят большой файл, а меньший не взят, их можно поменять: количество сохранится, занятое место не увеличится. Такое рассуждение называют доказательством обменом.

Важно учитывать всю формулировку. При вместимости 10 и размерах 4, 5, 6 лучший набор зависит от цели — выбери цель:

больше всего объектов

4 + 5два объекта, самые маленькие

наибольшая сумма

4 + 6 = 10самые маленькие дают только 9

наибольший отдельный объект

6один файл помещается целиком

Максимальное количество, максимальная сумма и максимальный отдельный элемент — разные цели.

«При максимальном количестве файлов укажите наибольший файл, который может быть сохранён». Это просто последний из выбранных?

Нет. Закрепим k − 1 самых маленьких файлов и найдём наибольший файл, который влезает в оставшееся место.

Максимальное количество равно четырём, и первоначально выбраны 8, 12, 15, 19. Но наибольший файл, который может оказаться среди четырёх сохранённых, — 22: набор 8, 12, 15, 22 занимает 57 ≤ 60.

Как получить это системно? Зафиксируем три самых маленьких файла — 8, 12, 15. Они занимают 35, для четвёртого остаётся 60 − 35 = 25. Из оставшихся файлов выбираем максимальный размер, не превышающий 25. Это 22.

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

Полная программа для формата S N в первой строке:

with open("26.txt") as f:    capacity, n = map(int, f.readline().split())    a = [int(f.readline()) for i in range(n)] a.sort()used = 0count = 0for size in a:    if used + size > capacity:        break    used += size    count += 1 fixed_sum = used - a[count - 1]limit = capacity - fixed_sumlargest = a[count - 1]for size in a[count - 1:]:    if size > limit:        break    largest = size print(count, largest)

Вторая половина программы — это рисунок выше: закрепили count − 1 самых маленьких и ищем наибольший файл, который помещается в оставшееся место limit.

Этот приём максимизирует один файл. Он не является способом максимизировать общую сумму выбранного набора.

«Важные файлы перенести в первую очередь, а на оставшееся место — как можно больше остальных». Что меняется?

Обязательные объекты кладут сразу, без выбора, а жадный выбор идёт по оставшемуся месту среди остальных. Пусть файл 34 обязателен. В записи второе поле — 1 у обязательного:

capacity = 60files = [(8, 0), (12, 0), (15, 0), (19, 0), (22, 0), (34, 1)]used = sum(size for size, must in files if must)count = sum(must for size, must in files)for size in sorted(s for s, must in files if not must):    if used + size > capacity:        break    used += size    count += 1print(count, capacity - used)

34 занимает своё место сразу, свободно 26: туда входят 8 и 12, а 15 уже нет. Всего три файла, свободно 6. Так же решаются задачи о грузовике, где «грузы массой от 310 до 320 кг грузят в первую очередь»: обязательность определяет условие, а не размер.

В строке файла не одно изделие, а партия: цена и количество. Как купить больше всего изделий?

Идти по партиям от дешёвых и брать из каждой сколько хватит денег: всю партию или money // price изделий.

Пусть на 500 рублей нужно купить как можно больше изделий A, а на остаток — как можно больше изделий B. Партии A: 5 штук по 20 и 10 штук по 35; партии B: 4 штуки по 25 и 30 штук по 15.

Для каждого типа идём по партиям от дешёвых к дорогим и из партии берём min(q, money // p) изделий: либо всю партию, либо сколько хватит денег. Деление нацело // отвечает на вопрос «сколько раз цена помещается в остаток».

money = 500lots = {"A": [(20, 5), (35, 10)], "B": [(25, 4), (15, 30)]}bought = {}for kind in "AB":    count = 0    for price, q in sorted(lots[kind]):        take = min(q, money // price)        count += take        money -= take * price        if take < q:            break    bought[kind] = countprint(bought["A"], bought["B"], money)

Все изделия A стоят 5 · 20 + 10 · 35 = 450, на остаток 50 покупаем 3 изделия B по 15 и остаётся 5. Почему после неполной партии можно остановиться? Денег не хватило даже на изделие этой партии, а следующие партии не дешевле.

Купить больше всего изделий, а среди таких покупок — больше изделий типа A. Как учесть второй критерий?

Количество находим как раньше — самыми дешёвыми. Потом перебираем, сколько из них будет изделий A: для каждого числа самая дешёвая покупка однозначна.

В подборке есть задачи с тремя приоритетами: купить максимальное общее количество изделий, затем максимальное количество изделий типа A, затем потратить минимальную сумму. Возьмём бюджет 36, цены изделий A — 4, 9, 14, изделий B — 3, 5, 6, 10.

Сначала определим максимальное общее количество. Все цены по возрастанию: 3, 4, 5, 6, 9, 10, 14. Пять самых дешёвых стоят 27, шесть — уже 37 > 36. Значит, нужно купить ровно пять изделий — это рассуждение прошлого шага.

Теперь спрашиваем: сколько из этих пяти может быть изделий A? Если берём x изделий A, изделий B должно быть 5 − x. Для фиксированного x самая дешёвая покупка состоит из x самых дешёвых A и 5 − x самых дешёвых B.

Значит, достаточно быстро находить суммы первых нескольких элементов. Для этого строят накопленные суммы, их также называют префиксными суммами: «префикс» — начальный участок последовательности. Для A = 4, 9, 14 получим PA = 0, 4, 13, 27: PA[0] — стоимость нуля изделий, PA[1] — одного самого дешёвого, PA[2] — двух, PA[3] — трёх. Каждая следующая накопленная сумма равна предыдущей плюс очередная цена. Для B: PB = 0, 3, 8, 14, 24.

Выбираем три A и два B. Остаток равен 1.

budget = 36a = sorted([4, 9, 14])b = sorted([3, 5, 6, 10])count = spent = 0for price in sorted(a + b):    if spent + price > budget:        break    spent += price    count += 1 prefix_a = [0]for price in a:    prefix_a.append(prefix_a[-1] + price)prefix_b = [0]for price in b:    prefix_b.append(prefix_b[-1] + price) best_a = best_cost = 0for count_a in range(count + 1):    count_b = count - count_a    if count_a > len(a) or count_b > len(b):        continue    cost = prefix_a[count_a] + prefix_b[count_b]    if cost <= budget:        best_a = count_a        best_cost = costprint(best_a, budget - best_cost)

Здесь нет перебора всех наборов покупок: перебирается только количество изделий A, а лучший набор с таким количеством строится однозначно.

«Каждый третий товар бесплатно»: какой именно товар окажется бесплатным?

Сначала понять, кто расставляет товары и кому выгодна расстановка: покупатель делает бесплатными самые дорогие возможные товары, продавец — самые дешёвые.

Одна фраза об акции ещё не определяет алгоритм. Выбери правило:

можно выбрать любые k товаров со скидкой

выгодно выбирать наиболее дорогие подходящие

в каждой паре скидка на дешёвый товар

нужно выгодно составить пары

в каждой тройке бесплатно самый дешёвый

нужно выгодно составить тройки

продавец сам переставляет товары

нужно учитывать цель продавца

скидка действует только выше порога

сначала выделяются подходящие товары

Рассмотрим конкретное правило:

Все товары нужно купить. Их можно разбить на тройки. В каждой полной тройке самый дешёвый товар бесплатный.

Цены: 100, 90, 80, 70, 60, 50, 40. Выгодные тройки — 100, 90, 80 и 70, 60, 50: бесплатно получаем 80 и 50, а 40 покупаем отдельно. Сумма всех цен 490, стоимость покупки 490 − 80 − 50 = 360. После сортировки по убыванию бесплатны элементы с индексами 2, 5, 8, …; третий параметр range — шаг:

prices = [70, 100, 40, 90, 50, 80, 60]prices.sort(reverse=True)free_sum = 0for i in range(2, len(prices), 3):    free_sum += prices[i]print(sum(prices) - free_sum)

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

Правило может работать и в пользу покупателя: если в каждой тройке бесплатен самый дорогой товар, к каждому бесплатному нужны два более дешёвых спутника. Тогда бесплатными выгодно сделать ⌊n / 3⌋ самых дорогих товаров, а спутников взять из дешёвых: для тех же цен бесплатны 100 и 90.

В подборках встречается и «каждый четвёртый товар в чеке за полцены». Покупатель ставит на 4-е, 8-е, … места самые дорогие товары, а касса, которая сортирует цены себе в пользу, — самые дешёвые. Для цен 100, 90, 80, 70, 60, 50, 40, 30 за полцены идут два товара: у покупателя 100 и 90 — он платит 425, у кассы 30 и 40 — 485.

prices = [60, 100, 30, 80, 50, 90, 40, 70]prices.sort(reverse=True)q = len(prices) // 4buyer = sum(prices) - sum(prices[:q]) // 2shop = sum(prices) - sum(prices[-q:]) // 2print(buyer, shop)

Если товары переставляет продавец и хочет дать скидку поменьше, скидка достаётся самым дешёвым из подходящих товаров: продавец ставит их на чётные места. Например, «скидка 25 % на каждый второй товар дороже 50 рублей»: из k таких товаров скидку получат ⌊k / 2⌋ самых дешёвых.

prices = [65, 300, 45, 120, 200, 80]big = sorted(p for p in prices if p > 50)discount = big[:len(big) // 2]total = sum(prices)numerator = 4 * total - sum(discount)print(discount, (numerator + 3) // 4)

• Больше всегоот самых маленьких, break после первого лишнего
• Наибольший при kзакрепить k − 1 самых маленьких
• Жадный выборобъяснить: оставляет не меньше возможностей
• Обязательныесначала они, потом выбор по остатку
• Партииmin(q, money // price)
• Скидкипокупатель — дорогие, продавец — дешёвые