Rozdíl mezi chamtivostí a dynamickým programováním

Dynamické programování je velmi specifické téma v programovacích soutěžích. Bez ohledu na to, kolik problémů s DP řešíte, stále vás to může překvapit. Ale stejně jako všechno ostatní v životě vás praxe zlepší ;-)

Další odpovědi na toto téma zmiňují několik pěkných úvodních textů, které vám pomohou pochopit, co je DP a jak to funguje. V několika následujících odstavcích se pokusím ukázat, jak řešit problémy s DP.

Poznámka: Proces vytváření řešení DP, který popisuji níže, se vztahuje přímo na všechny problémy Div1-250 a Div1–500 v aplikaci TopCoder, které lze vyřešit pomocí DP. Pevné problémy obvykle vyžadují určité úpravy, které můžete provést po nějaké praxi. Poznámka 2: Následující příklady kódu jsou psány v C ++. Pokud neznáte jazyk nebo si nejste jisti, zeptejte se mě v komentářích.

Opakujte a opakujte

Po přečtení některých úvodních textů o dynamickém programování (což vřele doporučuji), všechny příklady zdrojového kódu používají iterační metodu zdola nahoru (tj. Pomocí cyklů). Například výpočet nejdelší celkové délky dvou N řádků A a B je následující:

int dp [N + 1] [N + 1]; pro (int i = 0; i <= N; ++ i) dp [0] [i] = dp [i] [0] = 0; pro (int i = 1; i <= N; ++ i) (int j = 1; j <= N; ++ j) {dp [i] [j] = maximum (dp [i-1] [ j], dp [i] [j-1]); pokud (A [i-1] == B [j-1]) dp [i] [j] = maximum (dp [i] [j], dp [i-1] [j-1] +1); } int response = dp [N] [N];

Existuje několik důvodů pro její kódování:

  1. iterace je rychlejší než rekurze
  2. časová a prostorová složitost algoritmu je snadno vidět
  3. zdrojový kód je krátký a čistý

Když se podíváte na takový zdrojový kód, můžete pochopit, jak a proč to funguje, ale je těžké pochopit, jak to funguje. Největší průlom v učení dynamického programování je, když začnu přemýšlet o problémech shora dolů, nikoli o „zdola nahoru“. Na první pohled se to nezdá jako revoluční koncept, ale tyto dva přístupy jsou přímo přeloženy do dvou různých zdrojových kódů. Jeden používá iteraci (zdola nahoru) a druhý používá rekurzi (shora dolů). Druhá se také nazývá technika zapamatování. Obě řešení jsou víceméně rovnocenná a vždy se můžete změnit v jedno. V následujících odstavcích vám ukážu, jak najít řešení vašeho problému.

Problém motivace

Představte si, že máte sadu N vín na polici vedle sebe. Pro jednoduchost počítáme víno zleva doprava, protože jsou na polici, s celými čísly od 1 do N. Cena 1. vína je pi (cena různých vín se může lišit). Protože vína se každým rokem zlepšují, protože dnes je cena vína i-i * y ** pi, tj. Y více než v tomto roce, 1 rok.

Chcete prodat všechna vína, která máte, ale od tohoto roku chcete prodat jedno víno ročně. Dalším omezením je, že můžete prodávat pouze levá nebo pravá vína každý rok a není povoleno měnit uspořádání vína na polici (to znamená, že by měla být ve stejném pořadí jako dříve). ).

Pokud prodáváte vína přijatelným způsobem, chcete vědět, jaký zisk můžete dosáhnout. Například, pokud je cena vína (zleva doprava, pokud jsou v pořadí na polici) optimálním řešením: p1 = 1, p2 = 4, p3 = 2, p4 = 3. víno pro celkový zisk v řádu p1, p4, p3, p2 11 + 32 + 23 + 44 = 29

Špatné řešení

Po chvíli hraní s problémem se pravděpodobně rozhodnete, že chcete prodat drahá vína co nejdříve v nejlepším řešení. Možná přijdete s následující chamtivou strategií:

Prodávejte nejlevnější z obou (levých a pravých) vín dostupných každý rok.

Ačkoli strategie neříká, co dělat, když jsou dvě vína stejná, tato strategie se zdá být správná. V následujícím příkladu však bohužel tomu tak není. Je-li cena vína následující: p1 = 2, p2 = 3, p3 = 5, p4 = 1, p5 = 4 Chamtivá strategie je prodává za společnou výhodu objednávky p1, p2, p5, p4, p3 21 + 32 + 43 + 14 + 55 = 49 Pokud ale prodáme vína 21 + 42 + 13 + 34 + 55 = 50 za celkový zisk v řádu p1, p5, p4, p2, p3, můžeme dosáhnout dobrých výsledků. Příklad by vás měl přesvědčit, že problém není tak snadný, jak se zdá na první pohled, a mohu vám říci, že DP lze vyřešit.

Napište backtrack

Při hledání řešení vzpomínky na tento problém začínám s řešením backtrack, které vždy najde správnou odpověď. Řešení backtrack uvádí všechny správné odpovědi na problém a vybere nejlepší. U mnoha problémů lze takové řešení snadno najít. Některá omezení, která jsem vložil do svého řešení backtrack:

  • Měla by to být funkce, spočítat odpověď rekurzí
  • odpověď by měla být vrácena příkazem return, což znamená, že byste ji nikde neměli ukládat
  • všechny nelokální proměnné, které používají funkci, by měly být pouze pro čtení, což znamená, že funkce může měnit pouze lokální proměnné a její argumenty.

Takže pro problém s vínem vypadá řešení backtrack takto:

int p [N]; // řádek pro čtení cen vína // rok znamená běžný rok (začíná 1) // [být, en] označuje čas nevyužitých vín na zisku v regálech (int rok, int be, int en) {// žádné víno na polici, pokud (be> en) vrátí 0; // zkuste prodat levá nebo pravá vína, přepočítat // odpověď a vrátit lepší max (zisk (1 rok, + 1, en) + rok * p [být], zisk (rok + 1) , být, en-1) + rok * p [en]); }

Odpověď můžeme získat telefonicky:

int odpověď = přínos (1, 0, N-1); // N je celkový počet vín

Řešení testuje všechny možné objednávky prodeje vína. Pokud máte na začátku N víno, vyzkouší se možnosti 2 ^ N (každý rok máme 2 možnosti). Takže i když nyní dostaneme správnou odpověď, složitost algoritmu exponenciálně roste.

Dobře napsaná funkce backtrack by měla vždy ukazovat odpověď na dobře definovanou otázku. V našem případě vyvolává funkce zisku otázku: „Jak můžeme těžit z prodeje vína za ceny, které jsou v běžném roce a neprodávají se ve víně p?“ ** ** en], včetně? "

Vždy byste se měli zeptat na takové otázky, abyste se ujistili, že jste na zadní kartě udělali správnou věc a co dělá.

Minimalizujte stav argumentů funkce

V tomto kroku chci, abyste si mysleli, který z argumentů, které předáte této funkci, je zbytečný. Buď je můžeme stavět na jiných důkazech, nebo je vůbec nepotřebujeme. Pokud takové argumenty máte, nepředávejte je funkci. Prostě je spočítejte uvnitř funkce.

Ve prospěch výše uvedené funkce je rok argumentů nadbytečný. To se rovná počtu vín, která jsme již prodali, a jedno je celkový počet vín, která jsme prodali od začátku. Pokud zpočátku vytvoříme globální proměnnou jen pro čtení, která představuje celkový počet vín, můžeme funkci přepsat takto:

int N; // počet vín jen pro čtení na začátku int p [N]; // pole odečtených cen vína int přínos (int be, int en) {if (be> en) návrat 0; // počet prodaných vín (en-be + 1) int year = N - (en-be + 1) + 1; návratnost max (zisk (být + 1, en) + rok * p [být], zisk (být, en-1) + rok * p [en] jak je popsáno výše; }

Chci, abyste přemýšleli o rozsahu hodnot, které lze získat správným zadáním funkčních argumentů. V našem případě a každý z argumentů může obsahovat hodnoty od 0 do N-1. Při správném zadání předpokládáme, že <= en + 1. Existují různé O (N²) argumenty, které lze nazvat naší funkcí pomocí zápisu Big-O.

Cache to hned!

Nyní jsme 99% kompletní. Používáme malý trik, který nevyžaduje téměř žádné přemýšlení, aby se páteřní funkce O (2 ^ N) přeměnila na řešení času zapamatování na časovou složitost O (N²). Jak bylo uvedeno výše, existují pouze O (N²) různé argumenty, které lze volat naší funkcí. Jinými slovy, existují pouze O (N²) různé věci, které můžeme spočítat. Takže odkud pochází složitost času O (2 ^ N) a co se počítá? Odpověď: Složitost exponenciálního času je způsobena opakovanou rekurzí, a proto přepočítává stejné hodnoty znovu a znovu. Použijete-li výše uvedený kód libovolně pro N = 20 a vypočítáte, kolikrát je funkce volání argumentu = 10 a en = 10, získáte 92378. Je tedy ztráta času počítat. Na to odpovězte mnohokrát. Co musíme udělat, abychom to vylepšili, je to, že ji po výpočtu vypočítáme, a pokaždé, když funkce požaduje hodnotu v mezipaměti, nemusíme spouštět celou iteraci. Viz níže uvedený kód:

int N; // počet vín jen pro čtení na začátku int p [N]; // řádek mezipaměti pro čtení cen vína [N] [N]; // všechny hodnoty se zadávají v -1 (nebo cokoli, co si vyberete) int benefit (int be, int en) {if (be> en) return 0; // tyto dva řádky uloží den, pokud (cache [be] [en]! = -1) vrátí cache [be] [en]; int rok = N - (en-be + 1) + 1; // Nezapomeňte do mezipaměti novou odpověď při výpočtu nové návratové mezipaměti odpovědi [být] [en] = max (zisk (být + 1, en) + rok * p [být], zisk (být, en-1) + rok * p [en] ); }

A to je vše! S malým trikem tráví čas O (N²), protože O (N²) má různé argumenty a funkce O (1) pracuje s časovou složitostí pouze jednou. Poznámka: Pokud jsou hodnoty uloženy v mezipaměti, můžete s každým rekurzivním hovorem uvnitř funkce zacházet, jako by bylo provedeno na časovou složitost O (1).

Shrnutí

Abychom to shrnuli, pokud zjistíte, že problém lze vyřešit pomocí DP, zkuste vytvořit funkci backtrack, která vypočítá správnou odpověď. Pokuste se vyhnout zbytečným argumentům, minimalizujte rozsah možných argumentů funkčních argumentů a optimalizujte časovou složitost jediného volání funkce (nezapomeňte, že můžete používat rekurzivní volání jako v O (1)). Nakonec uložte hodnoty do mezipaměti a nezdvojnásobujte je. Konečná složitost řešení je: diversity_of_computer_values_the_function_can_be_called_w x x_komplexity_of_one_function_call.