Двоично търсене по отговора
Накратко: Двоичното търсене по отговора намира най-малката стойност (например капацитет), за която проверката „стига ли“ минава, когато отговорите са подредени като „не… не, да… да“.
Проблем
Колко голям камион да наемем
Куриерската фирма разнася пратките по маршрут: подред, в този ред, в който са по пътя. Камионът тръгва веднъж на ден и товари пратките една след друга, докато следващата не влезе. Тя остава за утре. Осемте пратки тежат 6, 9, 4, 7, 3, 8, 5 и 2 кг и трябва да стигнат до клиентите за 3 дни.
Колкото по-голям е камионът, толкова по-скъп е наемът на ден. Търси се най-малкият капацитет, с който пратките стигат навреме. Първото решение, което идва: пробвай всеки капацитет поред, от най-тежката пратка нагоре.
static int days(int[] weights, int capacity) { int days = 1; int load = 0; for (int weight : weights) { if (load + weight > capacity) { days++; load = 0; } load += weight; } return days;}int[] weights = {6, 9, 4, 7, 3, 8, 5, 2};int capacity = Arrays.stream(weights).max().getAsInt();int tries = 1;while (days(weights, capacity) > 3) { capacity++; tries++;}System.out.println("Проби: " + tries);System.out.println("Капацитет: " + capacity + " кг");Проби: 7Капацитет: 15 кгЗа осем пратки 7 проби минават. Но складът в града има по 1000 пратки (от 1 до 30 кг) за 5 работни дни. Поред, проверките товарят 3 089 000 пратки, докато стигнат отговора, а при два пъти повече пратки работата става около четири пъти повече. Ще го измериш по-долу.
Идеята
Подреден е отговорът
Пратките не са подредени. Подредено е нещо друго. Задай за всеки капацитет въпроса „стига ли?“ и подреди отговорите:
int[] weights = {6, 9, 4, 7, 3, 8, 5, 2};for (int capacity = 9; capacity <= 18; capacity++) { int d = days(weights, capacity); String answer = d <= 3 ? "да" : "не"; System.out.printf("%2d кг: %d дни, %s%n", capacity, d, answer);} 9 кг: 7 дни, не10 кг: 6 дни, не11 кг: 5 дни, не12 кг: 5 дни, не13 кг: 5 дни, не14 кг: 5 дни, не15 кг: 3 дни, да16 кг: 3 дни, да17 кг: 3 дни, да18 кг: 3 дни, даОтговорите са „не“, „не“, … и после само „да“. Щом капацитет X стига, всеки по-голям също стига: по-голям камион може да вози точно същите товари. Такава проверка се казва монотонна: от едно място нататък отговорът не се сменя.
А в линия „не… не, да… да“ първото „да“ се търси с двоично търсене, точно като първата цена ≥ 20 € в предишния урок: пробваш средата и изхвърляш половината. Това е двоично търсене по отговора: не търсиш в масив, а в обхвата на възможните отговори.
Обхватът е ясен. Капацитетът е поне колкото най-тежката пратка, иначе тя не влиза никога. И не трябва да е повече от сбора на всички: тогава всичко тръгва за един ден.
Виж го
Пробите по линията
static int minCapacity(int[] weights, int maxDays) { int lo = Arrays.stream(weights).max().getAsInt(); int hi = Arrays.stream(weights).sum(); while (lo < hi) { int mid = lo + (hi - lo) / 2; if (days(weights, mid) <= maxDays) { hi = mid; } else { lo = mid + 1; } } return lo;}int[] weights = {6, 9, 4, 7, 3, 8, 5, 2};System.out.println("Най-малкият капацитет: " + minCapacity(weights, 3) + " кг");Най-малкият капацитет: 15 кгstatic int days(int[] weights, int capacity) { int days = 1; int load = 0; for (int weight : weights) { if (load + weight > capacity) { days++; load = 0; } load += weight; } return days;}
static int minCapacity(int[] weights, int maxDays) { int lo = Arrays.stream(weights).max().getAsInt(); int hi = Arrays.stream(weights).sum(); while (lo < hi) { int mid = lo + (hi - lo) / 2; if (days(weights, mid) <= maxDays) { 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) <= maxDays. Ако отговорът е „да“, mid може да е най-малкото „да“ и остава: hi = mid. Ако е „не“, mid и всичко под него отпадат: lo = mid + 1.
Проверката days минава всички n пратки, а проби има около log₂ от сбора на теглата. Общо O(n log S), където S е сборът. Поред би било до S проби по n пратки.
Пробвай
Предвиди отговора
Същите осем пратки, но вече за 8 дни. Какво печата програмата?
int[] weights = {6, 9, 4, 7, 3, 8, 5, 2};System.out.println("Най-малкият капацитет: " + minCapacity(weights, 8) + " кг");lo започва от най-тежката пратка, 9 кг, а с 9 кг пратките тръгват за 7 дни: 7 ≤ 8, значи „да“. Всяка проба после казва „да“, hi слиза до lo и отговорът е 9 кг. По-малко не може: пратката от 9 кг не би влязла в камиона.
Пробвай
Попълни
Проверката казва „да“: с капацитет mid пратките стигат навреме. Какво става с hi?
static int minCapacity(int[] weights, int maxDays) {
int lo = Arrays.stream(weights).max().getAsInt();
int hi = Arrays.stream(weights).sum();
while (lo < hi) {
int mid = lo + (hi - lo) / 2;
if (days(weights, mid) <= maxDays) {
hi = ;
} else {
lo = mid + 1;
}
}
return lo;
}mid стига, но може да е най-малкият, който стига. Затова той остава в обхвата: hi = mid. Изхвърля се всичко над него, защото там отговорът със сигурност е „да“, а то не е най-малкото.
Пробвай
Намери грешката
Пратките трябва да стигнат за 6 дни. Търсенето казва 9 кг, а с 9 кг те стигат за 7 дни:
int[] weights = {6, 9, 4, 7, 3, 8, 5, 2};System.out.println("Най-малкият капацитет: " + minCapacity(weights, 6) + " кг");System.out.println(days(weights, minCapacity(weights, 6)) + " дни");Най-малкият капацитет: 9 кг7 дниИзбери реда с грешката.
При „да“ mid може да е отговорът, а hi = mid - 1 го изхвърля. Тук 10 кг е отговорът: пробата на 10 казва „да“, hi става 9, и в обхвата остава само 9, което е „не“. Цикълът свършва, без да го провери. Поправката е hi = mid: това е полуотвореният обхват от урока за двоичното търсене, и там при „да“ средата остава.
Идеята
Как познаваш такава задача
Знаците са три:
- търси се най-малкото (или най-голямото) X, при което нещо е възможно;
- за дадено X проверката е евтина: едно минаване, като
days; - проверката е монотонна: щом X става, всяко по-голямо X също става (или всяко по-малко).
Тогава не търсиш формула за X. Търсиш двоично в обхвата на възможните X, а проверката казва накъде.
Задачи от същия вид:
- най-малкото време, за което три принтера с различна скорост отпечатват 500 етикета за пратки. За дадено време се смята колко етикета излизат, а повече време не дава по-малко;
- най-малката скорост на лентата в склада, при която пакетите от смяната минават за 8 часа;
- най-голямото разстояние между автоматите за пратки по булеварда (упражнението долу). Тук търсиш най-голямото „да“.
По-точно, за любопитните
Защо проверката товари „колкото може“. Ако днес камионът вземе по-малко, отколкото може, утре остава повече. Да натовариш до горе никога не вреди, затова броят дни, който days дава, е най-малкият възможен за този капацитет.
Най-голямото „да“. Когато линията е „да… да, не… не“ и търсиш последното „да“, при „да“ се пише lo = mid, а при „не“ hi = mid - 1. Тогава средата трябва да се закръгли нагоре: lo + (hi - lo + 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 |
static int minCapacity(int[] weights, int maxDays) { int lo = Arrays.stream(weights).max().getAsInt(); int hi = Arrays.stream(weights).sum(); while (lo < hi) { int mid = lo + (hi - lo) / 2; if (days(weights, mid) <= maxDays) { hi = mid; } else { lo = mid + 1; } } return lo;}При 1000 пратки е 3 089 000 срещу 14 000. Над 1000 пратки „поред“ не се пуска наистина: то би товарило стотици милиони пратки.
Упражнение
Автоматите за пратки по булеварда
Реши задачата в редактора си.
Колкото може по-далеч. По булеварда има седем места за автомати за пратки, на 100, 400, 900, 1200, 2000, 2400 и 3100 м от началото. Фирмата слага 3 автомата и иска най-близките два да са колкото може по-далеч един от друг, за да покриват повече от града. Какво е най-голямото възможно най-малко разстояние?
Напиши проверка canPlace(spots, lockers, gap): слага автомат на първото място, а всеки следващ на първото място, което е поне gap метра след предишния, и казва дали стигат за всички. Търси двоично най-голямото gap, за което проверката казва „да“.
Най-голямото най-малко разстояние: 1100 мОще задачи
- Принтерите. Три принтера печатат по един етикет за 2, 3 и 7 секунди. За колко най-малко секунди отпечатват 500 етикета?
- Куриерите. Всеки куриер работи най-много 8 часа и взима поръчките подред. Поръчките отнемат 2, 3, 1, 4, 2, 5, 3 и 2 часа. Колко най-малко куриери трябват? А ако смяната е 6 часа?
- Колко прави проби. Добави брояч на пробите в
minCapacityи сравни с броя проби поред за същите пратки.
Тест