Как да разпознаеш DP задача в Python

Проблем

Кои заявки да приеме бусът?

Имаш един бус под наем. За утре има шест заявки за превоз, всяка с начало, край и цена. Бусът може да е само на едно място, затова две заявки, които се застъпват, не може да се вземат и двете. Кои да приемеш, за да вземеш най-много?

Първото, което хрумва, е алчно правило: най-скъпата заявка първо, после следващата, която не пречи. Или: тази, която свършва най-рано, за да остане повече време:

def greedy(jobs, rule):
    taken = []
    for job in sorted(jobs, key=rule):
        _, start, end, _ = job
        if all(end <= t[1] or t[2] <= start for t in taken):
            taken.append(job)
    return taken


def show(rule, taken):
    total = sum(job[3] for job in taken)
    names = ", ".join(job[0] for job in taken)
    print(f"{rule}: {names} = " + f"{total} €")

show("Най-скъпите първо", greedy(jobs, lambda job: -job[3]))
show("Най-ранният край първо", greedy(jobs, lambda job: job[2]))

Най-скъпите първо: летище, мебели = 180 €
Най-ранният край първо: пазар, офис, ремонт = 170 €

И двете правила оставят пари на масата: има разписание за повече. Да пробваш всички 2⁶ = 64 подмножества тук става, но при 60 заявки те са над милиард милиарда. Задачата е от същия вид като раницата и diff. Как да го познаеш сам, и как да построиш решението?

Идеята

Признаците

Една задача е за динамично програмиране, когато има три неща:

Въпросът е за най-доброто или за броя. „Най-много“, „най-малко“, „колко начина“, „може ли изобщо“. Ако се пита само „намери елемента“ или „подреди“, няма какво да се избира.
Оптималната подструктура. Най-доброто решение на цялото се строи от най-добрите решения на по-малки части. При буса: ако последната заявка е в най-доброто разписание, останалото е най-доброто разписание на заявките, които свършват преди нея.
Припокриващите се подзадачи. Едни и същи по-малки части се питат много пъти, както при наивния Фибоначи. При буса и „ремонт“, и „летище“ започват в 15 ч. и питат за едно и също: най-многото от заявките, които свършват до 15 ч.

Щом трите ги има, отговорът на всяка малка част се смята веднъж и се записва.

Идеята

Рецептата в пет стъпки

Състояние. Какво е една клетка: „best[i] е най-много пари от първите i заявки, подредени по края“. Добро състояние описва малката задача с едно-две числа.
Преход. Как клетката се смята от по-малки. За заявка i има два избора: пропусни я (best[i − 1]) или вземи я (цената ѝ + best[p], където p е колко заявки свършват до началото ѝ). best[i] е по-голямото.
Основа. Клетките, които не зависят от нищо: best[0] = 0, без заявки няма пари.
Ред. В какъв ред да пълниш, така че нужното вече да е готово: отляво надясно, защото i ползва само i − 1 и p < i.
Отговор. Коя клетка е отговорът: best[n]. Ако искаш и кои заявки, вървиш назад по изборите, както обратния път в diff.

Подреждането по края е част от състоянието: така заявките, съвместими с i-тата, са точно първите p и „най-доброто от тях“ е една клетка.

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

Същата рецепта работи и отгоре надолу: функция best(i), която вика best(i − 1) и best(p) и запомня резултата (виж запомнянето). Таблицата отдолу нагоре и рекурсията с памет смятат едни и същи клетки. Рекурсията е по-близо до думите на прехода, таблицата няма дълбок стек.

В Python запомнянето е един ред: @functools.cache над функцията. Пази лимита на рекурсията (1000 извиквания по подразбиране): за дълги редици таблицата е по-сигурна.

p може да се намери с двоично търсене по краищата, защото те са подредени: тогава цялото е O(n log n). Цикълът в урока е O(n) за всяка заявка, O(n²) общо, и за шест заявки е напълно достатъчен.

Виж го

Рецептата в код

def best_pay(jobs):
    jobs = sorted(jobs, key=lambda job: job[2])
    best = [0] * (len(jobs) + 1)
    for i in range(1, len(jobs) + 1):
        _, start, _, pay = jobs[i - 1]
        p = 0
        while jobs[p][2] <= start:
            p += 1
        skip = best[i - 1]
        take = pay + best[p]
        best[i] = max(skip, take)
    return best[-1]

sorted прави нов подреден списък, а _ е за полетата, които не ни трябват. Цикълът за p спира най-късно на самата i-та заявка, защото тя свършва след началото си.

jobs = [
    ("мебели", 9, 12, 80),
    ("летище", 15, 20, 100),
    ("пазар", 8, 10, 60),
    ("склад", 12, 17, 30),
    ("офис", 11, 13, 60),
    ("ремонт", 15, 19, 50),
]
print("Най-много: " + f"{best_pay(jobs)} €")

Най-много: 220 €

def best_pay(jobs):
    jobs = sorted(jobs, key=lambda job: job[2])
    best = [0] * (len(jobs) + 1)
    for i in range(1, len(jobs) + 1):
        _, start, _, pay = jobs[i - 1]
        p = 0
        while jobs[p][2] <= start:
            p += 1
        skip = best[i - 1]
        take = pay + best[p]
        best[i] = max(skip, take)
    return best[-1]

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

Шест заявки за един бус. Състояние: подреди ги по края; best[i] е най-много пари от първите i.
Основа: best[0] = 0, без заявки няма пари. Ред: отляво надясно, всяка клетка иска само клетки вляво от нея.
Заявка 1, пазар 8–10 ч., 60 €: нито една заявка не свършва преди нея, p = 0. Пропусни: best[0] = 0. Вземи: 60 + best[0] = 60. По-добре вземи я: best[1] = 60.
Заявка 2, мебели 9–12 ч., 80 €: нито една заявка не свършва преди нея, p = 0. Пропусни: best[1] = 60. Вземи: 80 + best[0] = 80. По-добре вземи я: best[2] = 80.
Заявка 3, офис 11–13 ч., 60 €: една свършва до 11 ч., p = 1. Пропусни: best[2] = 80. Вземи: 60 + best[1] = 120. По-добре вземи я: best[3] = 120.
Заявка 4, склад 12–17 ч., 30 €: 2 свършват до 12 ч., p = 2. Пропусни: best[3] = 120. Вземи: 30 + best[2] = 110. По-добре пропусни я: best[4] = 120.
Заявка 5, ремонт 15–19 ч., 50 €: 3 свършват до 15 ч., p = 3. Пропусни: best[4] = 120. Вземи: 50 + best[3] = 170. По-добре вземи я: best[5] = 170.
Заявка 6, летище 15–20 ч., 100 €: 3 свършват до 15 ч., p = 3. Пропусни: best[5] = 170. Вземи: 100 + best[3] = 220. По-добре вземи я: best[6] = 220.
Отговор: best[6] = 220 €. Назад по „вземи“ от нея излизат заявките: пазар, офис, летище.

220 € от пазар, офис и летище: повече и от най-скъпите първо, и от най-ранния край първо.

Пробвай

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

Колега е преписал прехода. Програмата казва:

def best_pay(jobs):
    jobs = sorted(jobs, key=lambda job: job[2])
    best = [0] * (len(jobs) + 1)
    for i in range(1, len(jobs) + 1):
        _, start, _, pay = jobs[i - 1]
        p = 0
        while jobs[p][2] <= start:
            p += 1
        skip = best[i - 1]
        take = pay + best[i - 1]
        best[i] = max(skip, take)
    return best[-1]

jobs = [
    ("мебели", 9, 12, 80),
    ("летище", 15, 20, 100),
    ("пазар", 8, 10, 60),
    ("склад", 12, 17, 30),
    ("офис", 11, 13, 60),
    ("ремонт", 15, 19, 50),
]
print("Най-много: " + f"{best_pay(jobs)} €")

Най-много: 380 €

Толкова не може: всички шест заявки заедно не се побират в един бус. На кой ред е грешката?

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

Идеята

Втора задача: паркингите по пътя

Камион кара от склада до последния паркинг на магистралата. Шофьорът трябва да почива: от един паркинг стига най-много до следващия или по-следващия. Всеки паркинг има такса. Колко най-малко ще плати, като спре и на последния?

Признаците: „най-малко“, а най-евтиният път до паркинг i минава през най-евтиния път до i − 1 или до i − 2. Рецептата:

Състояние: cost[i] е най-малкото, платено до паркинг i, като спре на него.
Преход: cost[i] = таксата на i + min(cost[i − 1], cost[i − 2]).
Основа: от склада стига до паркинг 0 или направо до паркинг 1, затова cost[0] и cost[1] са само таксите им.
Ред: отляво надясно.
Отговор: cost на последния паркинг.

def min_fees(fee):
    cost = [0] * len(fee)
    cost[0] = fee[0]
    cost[1] = fee[1]
    for i in range(2, len(fee)):
        cost[i] = fee[i] + min(cost[i - 1], cost[i - 2])
    return cost[-1]

parking = [4, 9, 3, 12, 5, 2, 10, 6]
print("Най-малко: " + f"{min_fees(parking)} €")

Най-малко: 20 €

Пробвай

Предвиди изхода

Четири паркинга с такси 5, 1, 4 и 2 €:

def min_fees(fee):
    cost = [0] * len(fee)
    cost[0] = fee[0]
    cost[1] = fee[1]
    for i in range(2, len(fee)):
        cost[i] = fee[i] + min(cost[i - 1], cost[i - 2])
    return cost[-1]

parking = [5, 1, 4, 2]
print("Най-малко: " + f"{min_fees(parking)} €")

Отговор

Най-малко: 12 €

Най-малко: 3 €

Най-малко: 8 €

Идеята

Трета задача: текст без интервали

Клиентите пишат в търсачката „лятнаразпродажба“, без интервали, както в хаштаг. Може ли текстът да се раздели на думи от речника?

Признакът е „може ли“: да или не. Рецептата:

Състояние: ok[i] е „първите i букви се разделят на думи“.
Преход: ok[i] е истина, ако има j < i с ok[j] и буквите от j до i са дума от речника.
Основа: ok[0] е истина: празното начало винаги се разделя.
Ред: i расте.
Отговор: ok[n].

def can_split(text, words):
    n = len(text)
    ok = [False] * (n + 1)
    ok[0] = True
    for i in range(1, n + 1):
        ok[i] = any(ok[j] and text[j:i] in words for j in range(i))
    return ok[n]

words = {
    "лятна", "лят", "на", "разпродажба", "раз", "продажба", "обувки", "за", "деца",
}
for text in ["лятнаразпродажба", "обувкизадеца", "обувкизабебета"]:
    print(text + ": " + ("да" if can_split(text, words) else "не"))

лятнаразпродажба: да
обувкизадеца: да
обувкизабебета: не

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

За всяко i цикълът пробва до i места за j, а всяко парче се изрязва и търси в речника. Изрязването копира буквите (резенът text[j:i] прави нов низ), затова цялото е до O(n³) за текст с n букви. Ако най-дългата дума в речника е L букви, j трябва да е само между i − L и i, и времето пада до O(n · L²). Истинските търсачки ползват trie от думите на речника: вървят по буквите от j нататък и спират, щом trie-то свърши.

Пробвай

Попълни прехода

def can_split(text, words):
    n = len(text)
    ok = [False] * (n + 1)
    ok[0] = True
    for i in range(1, n + 1):
        ok[i] = any( for j in range(i))
    return ok[n]

Идеята

Прилича на DP, а не е

Не всяка задача за „най-много“ иска таблица.

Алчното понякога стига. Ако всички заявки за буса плащат еднакво, въпросът става „колко най-много заявки“, и правилото „най-ранният край първо“ дава точно най-доброто, за O(n log n) и без таблица. Кога алчното е доказано вярно и защо, е в следващия модул. Знакът: при всяка стъпка един избор е винаги поне толкова добър, колкото всеки друг.
Графът няма ред. Най-краткият път в града прилича на DP: разстоянието до кръстовище се строи от разстоянията до съседите. Но улиците правят кръгове, и „до A“ зависи от „до B“, а „до B“ от „до A“. Няма ред, в който да пълниш таблицата отляво надясно. Затова там е Dijkstra: той намира реда в движение.
Без припокриване. Ако подзадачите не се повтарят, както при merge sort, запомнянето не пести нищо. Това е „разделяй и владей“.

Проверката е стъпка 4 от рецептата: ако не можеш да кажеш в какъв ред да пълниш, задачата вероятно е за граф.

Упражнение

Рекламните табла

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

Табла. По булеварда има седем рекламни табла, номерирани от 1, с месечен наем 120, 90, 60, 150, 80, 40 и 130 €. Две съседни табла се закриват едно друго, затова не може да се дадат под наем и двете. Напиши решението по рецептата: изведи най-големия наем и кои табла да се дадат:

Най-много: 400 €
Табла: 1, 4, 7

Подсказка: състоянието е „най-много от първите i табла“, а преходът е същият избор като при буса: пропусни табло i или го вземи заедно с най-доброто до i − 2.

Още задачи

Колко начина. По колко начина камионът може да стигне до последния паркинг (по един или два паркинга напред)? Сменя се само преходът: сума вместо минимум.
Разделянето поименно. Изведи и самите думи на „лятнаразпродажба“: пази за всяко ok[i] откъде е дошло.
Заявките поименно. Върни от bestPay и кои заявки да приемеш: вървиш назад от best[n], както на сцената.

Тест

Провери се

1. Кой въпрос най-вероятно е DP задача?Подреди продуктите по ценаИма ли в списъка поръчка с номер 1042?Колко най-малко монети от 1, 3 и 4 цента дават 6 цента?

2. В задачата с буса заявките се подреждат по края. Защо?Защото така прави и алчното правилоТогава заявките, които свършват преди i-тата, са поредните в началото: best[p] ги обхващаБез подреждане програмата не се компилира

3. Какво е основата при текста без интервали?ok[n] = trueok[0] = true: празният текст винаги се разделяok[0] = false

4. Защо най-краткият път в града с Dijkstra не се пише като таблица отляво надясно?Защото таблицата би била твърде голямаУлиците правят кръгове: няма ред, в който всяка клетка зависи само от готови клеткиЗащото Dijkstra не търси най-краткото

5. Пропускаш ли нещо, ако в прехода take = pay + best[i − 1]?Да: губиш основата best[0]Да: може да вземеш заявка, която се застъпва с вече взетаНе, само е по-бавно

Как да разпознаеш DP задача

Бисквитки