Жадные алгоритмы. Задача о резервных копиях.

Определение

Задача о резервных копиях: имеется система, состоящая из N хранилищ, различной ёмкости. В i-ом хранилище можно разместить Ai блоков информации. Хранение блока считается надежным, если в хранилище есть 2 его копии. Требуется определить наибольшее кол-во надежных блоков, которое можно разместить во всех хранилищах   Для объяснения решение этой задачи, рассматривают эквивалентную задачу про камушки:

Есть N кучек камней, каждым ходом можно забрать по одинаковому кол-ву камней из двух кучек. Найти такой порядок ходов, при котором в игре останется минимальное кол-во камней(либо во всех по 0, либо только в 1, и то минимум).

Стратегия

• Выбираем наибольшую и наименьшую по кол-ву камней кучи и берём из них по 1 камню.
• Продолжаем выполнять действие пока есть хотя бы 2 кучи, в которых есть камни.

Таким образом, кол-во ходов и будет ответом к задаче, потому что показывает максимальное кол-во пар, которое можно разместить в хранилище.

def max_reliable_blocks(storages):  
    # Сортировка хранилищ по убыванию ёмкости  
    storages.sort(key=lambda x: x['capacity'], reverse=True)  
	  
    total_blocks = 0  
    for storage in storages:  
        capacity = storage['capacity']  
        blocks_needed = min(capacity // 2, 1)  # Рассчитываем, сколько блоков можно разместить  
        total_blocks += blocks_needed * 2  # Добавляем блоки, умноженные на 2 (для двух копий)  
        capacity -= blocks_needed * 2  # Уменьшаем ёмкость хранилища  
	  
        if capacity <= 0:  
            break  # Если ёмкости осталось мало, прерываем цикл  
	  
    return total_blocks

Вся СУТЬ задачи в том, что минимальное возможное действие - оставить файл размером 1 в двух хранилищах. Ограничение в том, что места обязательно должны быть разные. Если у нас три хранилища с размерами 3 4 5 и мы оставим по 3 копии в (1) и (2) хранилище, то получим 0 1 5. Затем остаётся единственный вариант - оставить 1 копию в (2) и (3) хранилище с результатом 0 0 4. У нас ещё целых четыре места, но копии нельзя разместить в одном хранилище. В сумме мы разместили всего 4 копии, хотя с наилучшей стратегией можно разместить аж 6 копий