Двоично търсене по отговора в Python

Проблем

Колко голям камион да наемем

Куриерската фирма разнася пратките по маршрут: подред, в този ред, в който са по пътя. Камионът тръгва веднъж на ден и товари пратките една след друга, докато следващата не влезе. Тя остава за утре. Осемте пратки тежат 6, 9, 4, 7, 3, 8, 5 и 2 кг и трябва да стигнат до клиентите за 3 дни.

Колкото по-голям е камионът, толкова по-скъп е наемът на ден. Търси се най-малкият капацитет, с който пратките стигат навреме. Първото решение, което идва: пробвай всеки капацитет поред, от най-тежката пратка нагоре.

def days(weights, capacity):
    days = 1
    load = 0
    for weight in weights:
        if load + weight > capacity:
            days += 1
            load = 0
        load += weight
    return days

weights = [6, 9, 4, 7, 3, 8, 5, 2]
capacity = max(weights)
tries = 1
while days(weights, capacity) > 3:
    capacity += 1
    tries += 1
print(f"Проби: {tries}")
print(f"Капацитет: {capacity} кг")

Проби: 7
Капацитет: 15 кг

За осем пратки 7 проби минават. Но складът в града има по 1000 пратки (от 1 до 30 кг) за 5 работни дни. Поред, проверките товарят 3 089 000 пратки, докато стигнат отговора, а при два пъти повече пратки работата става около четири пъти повече. Ще го измериш по-долу.

Идеята

Подреден е отговорът

Пратките не са подредени. Подредено е нещо друго. Задай за всеки капацитет въпроса „стига ли?“ и подреди отговорите:

weights = [6, 9, 4, 7, 3, 8, 5, 2]
for capacity in range(9, 19):
    d = days(weights, capacity)
    answer = "да" if d <= 3 else "не"
    print(f"{capacity:2} кг: {d} дни, {answer}")

 9 кг: 7 дни, не
10 кг: 6 дни, не
11 кг: 5 дни, не
12 кг: 5 дни, не
13 кг: 5 дни, не
14 кг: 5 дни, не
15 кг: 3 дни, да
16 кг: 3 дни, да
17 кг: 3 дни, да
18 кг: 3 дни, да

Отговорите са „не“, „не“, … и после само „да“. Щом капацитет X стига, всеки по-голям също стига: по-голям камион може да вози точно същите товари. Такава проверка се казва монотонна: от едно място нататък отговорът не се сменя.

А в линия „не… не, да… да“ първото „да“ се търси с двоично търсене, точно като първата цена ≥ 20 € в предишния урок: пробваш средата и изхвърляш половината. Това е двоично търсене по отговора: не търсиш в масив, а в обхвата на възможните отговори.

Обхватът е ясен. Капацитетът е поне колкото най-тежката пратка, иначе тя не влиза никога. И не трябва да е повече от сбора на всички: тогава всичко тръгва за един ден.

Виж го

Пробите по линията

def min_capacity(weights, max_days):
    lo = max(weights)
    hi = sum(weights)
    while lo < hi:
        mid = (lo + hi) // 2
        if days(weights, mid) <= max_days:
            hi = mid
        else:
            lo = mid + 1
    return lo

weights = [6, 9, 4, 7, 3, 8, 5, 2]
print(f"Най-малкият капацитет: {min_capacity(weights, 3)} кг")

Най-малкият капацитет: 15 кг

def days(weights, capacity):
    days = 1
    load = 0
    for weight in weights:
        if load + weight > capacity:
            days += 1
            load = 0
        load += weight
    return days


def min_capacity(weights, max_days):
    lo = max(weights)
    hi = sum(weights)
    while lo < hi:
        mid = (lo + hi) // 2
        if days(weights, mid) <= max_days:
            hi = mid
        else:
            lo = mid + 1
    return lo

Стъпка по стъпка, с думи

8 пратки, най-много 3 дни. Капацитетът е поне 9 кг (най-тежката пратка) и най-много 44 кг (всичко за един ден). Отговорът е една от тези 36 стойности.
mid = 26 кг: камионът товари подред, 2 дни. 2 ≤ 3: да. Всеки капацитет над 26 също е „да“, затова hi = 26.
mid = 17 кг: камионът товари подред, 3 дни. 3 ≤ 3: да. Всеки капацитет над 17 също е „да“, затова hi = 17.
mid = 13 кг: 5 дни, повече от 3: не. Всеки капацитет под 13 също е „не“, затова lo = 14.
mid = 15 кг: камионът товари подред, 3 дни. 3 ≤ 3: да. Всеки капацитет над 15 също е „да“, затова hi = 15.
mid = 14 кг: 5 дни, повече от 3: не. Всеки капацитет под 14 също е „не“, затова lo = 15.
lo и hi се срещат на 15 кг: първото „да“ на линията. 5 проверки, вместо капацитетите един по един.

Това е долната граница от предишния урок. Само че вместо prices[mid] < target има въпрос, на който отговаря цяла функция: days(weights, mid) <= max_days. Ако отговорът е „да“, mid може да е най-малкото „да“ и остава: hi = mid. Ако е „не“, mid и всичко под него отпадат: lo = mid + 1.

Проверката days минава всички n пратки, а проби има около log₂ от сбора на теглата. Общо O(n log S), където S е сборът. Поред би било до S проби по n пратки.

Пробвай

Предвиди отговора

Същите осем пратки, но вече за 8 дни. Какво печата програмата?

weights = [6, 9, 4, 7, 3, 8, 5, 2]
print(f"Най-малкият капацитет: {min_capacity(weights, 8)} кг")

Отговор

Най-малкият капацитет: 9 кг

Най-малкият капацитет: 6 кг

Най-малкият капацитет: 2 кг

Пробвай

Попълни

Проверката казва „да“: с капацитет mid пратките стигат навреме. Какво става с hi?

def min_capacity(weights, max_days):
    lo = max(weights)
    hi = sum(weights)
    while lo < hi:
        mid = (lo + hi) // 2
        if days(weights, mid) <= max_days:
            hi = 
        else:
            lo = mid + 1
    return lo

Пробвай

Намери грешката

Пратките трябва да стигнат за 6 дни. Търсенето казва 9 кг, а с 9 кг те стигат за 7 дни:

weights = [6, 9, 4, 7, 3, 8, 5, 2]
print(f"Най-малкият капацитет: {min_capacity(weights, 6)} кг")
print(days(weights, min_capacity(weights, 6)), "дни")

Най-малкият капацитет: 9 кг
7 дни

Избери реда с грешката.

Идеята

Как познаваш такава задача

Знаците са три:

търси се най-малкото (или най-голямото) X, при което нещо е възможно;
за дадено X проверката е евтина: едно минаване, като days;
проверката е монотонна: щом X става, всяко по-голямо X също става (или всяко по-малко).

Тогава не търсиш формула за X. Търсиш двоично в обхвата на възможните X, а проверката казва накъде.

Задачи от същия вид:

най-малкото време, за което три принтера с различна скорост отпечатват 500 етикета за пратки. За дадено време се смята колко етикета излизат, а повече време не дава по-малко;
най-малката скорост на лентата в склада, при която пакетите от смяната минават за 8 часа;
най-голямото разстояние между автоматите за пратки по булеварда (упражнението долу). Тук търсиш най-голямото „да“.

По-точно, за любопитните

Защо проверката товари „колкото може“. Ако днес камионът вземе по-малко, отколкото може, утре остава повече. Да натовариш до горе никога не вреди, затова броят дни, който days дава, е най-малкият възможен за този капацитет.

Най-голямото „да“. Когато линията е „да… да, не… не“ и търсиш последното „да“, при „да“ се пише lo = mid, а при „не“ hi = mid - 1. Тогава средата трябва да се закръгли нагоре: (lo + hi + 1) // 2. Иначе при lo и hi едно до друго средата е lo, lo = mid не мърда и цикълът не спира. Същата граница като в урока за двоичното търсене, от другата страна.

Отговор с дроб. Ако X е например скорост в метри в секунда, обхватът е от реални числа и lo и hi никога не стават равни. Тогава цикълът върви определен брой пъти, например 60: всеки път обхватът се разполовява, и след 60 разполовявания е по-малък от всяка точност, която те интересува.

Виж го

Измери: поред срещу двоично

Пратки от 1 до 30 кг, 5 дни. Операцията е една пратка, натоварена при проверка. Поред броят на пробите расте с n, и всяка товари n пратки: O(n²). Двоичното прави около log₂ S проби: O(n log n).

Всеки капацитет поред O(n²)
Двоично търсене по капацитета O(n log n)

Алгоритъм	n = 10	n = 100	n = 1000	n = 10 000	n = 100 000
Всеки капацитет поред	90	28 800	3 089 000	≈ 308 900 000	≈ 30 890 000 000
Двоично търсене по капацитета	70	1100	14 000	180 000	2 100 000

Кодът се пуска в твоя браузър на JavaScript. Броят операции е същият на всеки език, защото алгоритъмът е същият. Времето зависи от машината, затова е само за сравнение. „≈“ е оценка по кривата: толкова голямо n не пускаме, за да не замръзне страницата.

def min_capacity(weights, max_days):
    lo = max(weights)
    hi = sum(weights)
    while lo < hi:
        mid = (lo + hi) // 2
        if days(weights, mid) <= max_days:
            hi = mid
        else:
            lo = mid + 1
    return lo

При 1000 пратки е 3 089 000 срещу 14 000. Над 1000 пратки „поред“ не се пуска наистина: то би товарило стотици милиони пратки.

Упражнение

Автоматите за пратки по булеварда

Реши задачата в редактора си.

Колкото може по-далеч. По булеварда има седем места за автомати за пратки, на 100, 400, 900, 1200, 2000, 2400 и 3100 м от началото. Фирмата слага 3 автомата и иска най-близките два да са колкото може по-далеч един от друг, за да покриват повече от града. Какво е най-голямото възможно най-малко разстояние?

Напиши проверка can_place(spots, lockers, gap): слага автомат на първото място, а всеки следващ на първото място, което е поне gap метра след предишния, и казва дали стигат за всички. Търси двоично най-голямото gap, за което проверката казва „да“.

Най-голямото най-малко разстояние: 1100 м

Още задачи

Принтерите. Три принтера печатат по един етикет за 2, 3 и 7 секунди. За колко най-малко секунди отпечатват 500 етикета?
Куриерите. Всеки куриер работи най-много 8 часа и взима поръчките подред. Поръчките отнемат 2, 3, 1, 4, 2, 5, 3 и 2 часа. Колко най-малко куриери трябват? А ако смяната е 6 часа?
Колко прави проби. Добави брояч на пробите в min_capacity и сравни с броя проби поред за същите пратки.

Тест

Провери се

1. Защо двоичното търсене по капацитета дава верен отговор?Защото капацитетите са цели числаЗащото пратките са подредени по теглоЗащото щом капацитет X стига, всеки по-голям също стига: отговорите са „не… не, да… да“

2. Пробата казва „да“ при 26 кг. Какво става с hi?lo = 27hi = 26: 26 може да е отговорът, търсим дали има по-малъкhi = 25: 26 вече е проверено

3. Между кои стойности се търси капацитетът?От най-леката пратка до най-тежкатаОт 0 до 1000От най-тежката пратка до сумата на всички

4. Коя задача се решава с двоично търсене по отговора?Най-евтиният продукт в списъкНай-малкото време, за което три принтера отпечатват 500 поръчкиПродуктите, подредени по цена

Двоично търсене по отговора

Бисквитки