Нахождение наименьшего объёма баков для полной отливки всех сосудов

Условие

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

• Сосуды отливаются последовательно, в том же порядке, в каком они заданы.
• Каждый сосуд должен быть отлит целиком.
• Если текущий сосуд не помещается в частично заполненный бак, берётся следующий пустой бак.

Пример: Имеем 4 бака и сосуды с объёмами: 1 3 2 4 10 8 4 2 5 3. Достаточно сделать баки объёмом 12 литров, тогда перелив возможен так: 1 3 2 4 | 10 | 8 4 | 2 5 3

Ответ

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

def min_capacity(volumes, tanks):
    if tanks <= 0 or any(v < 0 for v in volumes):
        raise ValueError('Некорректные данные')
    if not volumes:
        return 0
    low, high = max(volumes), sum(volumes)
    def fits(capacity):
        used, load = 1, 0
        for volume in volumes:
            if load + volume > capacity:
                used += 1
                load = 0
            load += volume
        return used <= tanks
    while low < high:
        middle = low + (high - low) // 2
        if fits(middle):
            high = middle
        else:
            low = middle + 1
    return low

Для примера минимум 12: при 11 понадобится пять баков. Проверка монотонна — увеличение ёмкости не ухудшает возможность размещения. Время O(n log S), память O(1), где S — сумма объёмов; дробные объёмы требуют иной точности поиска.