При разгледување на разни проблеми, често се случува решението на еден проблем да зависи од решавањето на помали верзии од истиот тој проблем. На пример, доколку на една маса имаме 10 книги и знаеме дека во нив терминот “херој” се споменува вкупно 1000 пати (во сите книги заедно), и некој донесе нова (11-та) книга и не праша колку сега вкупно пати се споменува терминот “херој” во 11-те книги кои ги имаме на масата, нема потреба повторно да ги разгледуваме сите книги, туку доволно е само да изброиме колку пати се споменува “херој” во 11-тата книга и тој број да го додадеме на бројот (1000) на споменувања на “херој” во првите 10 книги.

Во ова предавање ќе зборуваме за динамичко програмирање, што претставува техника за решавање на сложени проблеми преку нивно разбивање на помали проблеми, решавање на истите, и потоа комбинирање на резултатите со цел добивање на решението на оригиналниот проблем. Притоа, ќе забележиме дека при користењето на оваа техника, важно е да ги паметиме решенијата на помалите проблеми (со користење на низи, мапи, и слично), и истите да не ги пресметуваме по повеќе пати – како што направивме во случајот со книгите (споменат погоре).

Како едноставен пример за динамичко програмирање можеме да го споменеме и следниот коментар, оригинално објавен на сајтот Quora. Нека запишеме 1+1+1+1+1+1+1+1 на парче хартија, и нека замолиме некој (на пример, некое дете) да го пресмета збирот. По некое време, ќе добиеме одговор “Осум”. Сега, нека запишеме “1+” лево од изразот кој веќе го имаме дадено, и прашаме колку е сега одговорот. Нормално, веднаш ќе добиеме одговор “Девет”, бидејќи нема потреба повторно да се пресметуваат работите кои веќе ги знаеме. Со други зборови, динамичко програмирање е само израз кој означува дека ќе паметиме одредени вредности за да зачуваме време во иднина, наместо да ги пресметуваме истите по повеќе пати.

Најмал број во низа

Нека ни е дадена низа од неколку цели броеви, и нека треба да напишеме програма која ефикасно ќе дава одговор на прашањето “Кој е најмал број од првите X елементи во низата?”. Со други зборови, ако имаме низа од 10 цели броеви [15, 14, 12, 13, 9, 7, 13, 13, 14, 100], најмалиот број од првите четири броеви е 12, најмалиот број од првите девет броеви е 7, итн. Решавајќи го овој едноставен проблем, ќе се запознаеме со основните концепти на динамичкото програмирање, и најчестите грешки кои се прават при користењето на оваа техника на решавање.

Веројатно, имајќи ги во предвид двата примера наведени погоре (со книгите, и со собирањето на броеви), забележавте дека, доколку знаеме кој е најмалиот број до одредена позиција (на пример, најмалиот број од првите пет наведени во низата), лесно можеме да го пронајдеме најмалиот број вклучувајќи ја и следната позиција (најмалиот број од првите шест е, или шестиот број во низата, или најмалата вредност која веќе ја имаме пресметано за првите пет броеви). Притоа, решението на самиот проблем е едноставно – имено, треба само да ја повториме постапката наведена погоре за сите позиции. За чување на резултатите до одредена позиција, можеме да користиме низа. Да го видиме решението.

#include <iostream>
using namespace std;


int main()
{
     int N = 10;
     int numbers[] = {15, 14, 12, 13, 9, 7, 13, 13, 14, 100};
     
     //dinamicko programiranje
     int smallest[N];
     smallest[0] = numbers[0]; //za prvata pozicija e jasno koj e najmaliot broj
     
     for(int i=1; i < N; i++)
     {
          //najmaliot do pozicija "i" e najmaliot do prethodnata pozicija
          //ili noviot broj, koj se naogja tocno na pozicija "i"
          smallest[i] = min(smallest[i-1], numbers[i]);
     }
     
     //pechatenje na nekolku vrednosti
     cout << smallest[3] << endl; //12, bidejki 12 e najmal od prvite 4 (0-3)
     cout << smallest[8] << endl; //7, bidejki 7 e najmaliot broj od prvite 9
     return 0;
}

Решението дадено погоре е класичен пример за тоа како изгледа решавање на одреден проблем со динамичко програмирање - изворен код кој е краток, и лесен за разбирање. Исто, забележете како го искористивме фактот што го знаеме решението за помали проблеми (до X-та позиција), за решавање на поголем проблем (до (X+1)-ва позиција). Кај повеќето проблеми, ова го правиме со користење на дополнителна меморија - во случајов, имаме низа за чување на најмалите вредности до одредена позиција. Дополнително, слично како и при решавање на проблеми со помош на рекурзија, и кај динамичкото програмирање најчесто имаме т.н. основен или тривијален случај, чиј резултат веќе го знаеме. Во случајот даден погоре, тривијален случај е најмалата вредност до првиот елемент. Имено, бидејќи се работи за само една вредност, јасно е дека таа вредност е и најмалата до таа позиција во низата.

Во однос на сложеноста, решението дадено погоре има линеарна сложеност O(N), бидејќи имавме for циклус кој што ги измина сите N позиции во низата. Но, она што е интересно е дека, од кога еднаш ги изминавме елементите и ја пополнивме низата smallest[] со потребните вредности, давањето одговор за тоа кој е најмалиот елемент до одредена позиција X се случува во константно време O(1), па можно е, без да правиме дополнителни пресметки, веднаш да даваме одговор и на повеќе вакви прашања: кој е најмалиот број од првите 5 елементи, кој е најмал број од првите 9 елементи, кој е најмалиот број од сите елементи, итн - преку едноставен пристап до соодветните вредности од низата smallest[].

За крај, да наведеме уште еднаш дека, при решавање на проблеми со техниката на динамичко програмирање, го користиме фактот дека одреден проблем може да се реши преку решавање на помали проблеми (често, слични на оригиналниот). Во однос на терминологијата која што се користи кај динамичко програмирање, за оригиналниот проблем и за помалите верзии од истиот се користи терминот “состојба”. Па така, при дискутирање на решенијата, зборуваме за користење на решението за одредена состојба (на пример, најмалиот број од првите X), за решавање на друга состојба (најмалиот број од првите X+1).

Но, тука е важно да внимаваме на една од најчестите грешки која што се прави при решавањето на задачи со динамичко програмирање. Имено, зависно од тоа колку дополнителна меморија користиме или како ги користиме помалите проблеми за решавање на оригиналниот проблем, понекогаш е многу тешко да го прошириме решението кое го имаме за решавање на други проблеми. На пример, со програмата дадена погоре не можеме да дадеме одговор на прашањето “Кој е најмалиот број во низата, ако ги разгледуваме само броевите од 3та до 7ма позиција”. Напротив, решението кое го напишавме очекува дека секогаш ќе разгледуваме вредности почнувајќи од првата позиција, па до одредена X-та позиција, и потребно е да напишеме друго решение доколку сакаме нашата програма да дава решенија и за други интервали од позиции (интересно, постои решение користејќи динамичко програмирање и за тој проблем). Поради ова, запаметете дека секогаш треба добро да го сфатиме проблемот кој го решаваме пред да почнеме со програмирање, бидејќи понекогаш е тешко да правиме измени на алгоритмите во средина на нивна имплементација. Најлошото нешто што можеме да го направиме е да изгубиме време решавајќи погрешен проблем - иако тој, на почеток, ни изгледа сличен на вистинскиот.

Фибоначиеви броеви

Фибоначиеви броеви се броеви од т.н. секвенца на фибоначиеви броеви, и истите се карактеристични по тоа што секој број (освен првите два) е збир на двата броеви од секвенцата кои доаѓаат пред него. Првите неколку фибоначиеви броеви се: 1, 1, 2, 3, 5, 8, 13, 21, итн. Забележете дека првите два броја се еднакви на 1, а секој следен број е збир од претходните два (на пример, 13 = 5+8). Во претходното предавање, каде што зборувавме за рекурзија, видовме дека можеме да напишеме функции кои се повикуваат самите себеси. Да напишеме рекурзивна функција која го открива N-тиот фибоначиев број:

int fibonacci(int N)
{
     if (N == 1 || N == 2)
     {
          return 1;
     }
     
     //inaku, N-tiot fibonaciev broj e zbir
     //od prethodnite dva
     return fibonacci(N-1) + fibonacci(N-2);
}

Алгоритамот е едноставен. Првите два фибоначиеви броеви (N=1 и N=2) се еднакви на 1, а за останатите (N > 2) важи дека N-тиот фибоначиев број е збир од (N-1)виот фибоначиев број и (N-2)риот фибоначиев број. Овој алгоритам е точен, но сепак има еден проблем. Имено, за поголеми вредности на N тој работи исклучително бавно - бидејќи истиот по неколку пати пресметува одредени состојби. Да видиме што се случува кога ја повикуваме нашата функција за, на пример, N=6. Имено, тука функцијата ќе се повика себеси со вредности N=5 и N=4, бидејќи:

fibonacci(6) = fibonacci(5) + fibonacci(4)

Функцијата ќе продолжи да се повикува и понатаму, рекурзивно. Така, ако во горната равенка продолжиме со повиците (користејќи дека fibonacci(5) = fibonacci(4) + fibonacci(3)), го добиваме следното:

fibonacci(6) = fibonacci(5) + fibonacci(4)
fibonacci(6) = [ fibonacci(4) + fibonacci(3) ] + fibonacci(4)

Дали можете да забележите што произлегува од тука? Имено, функцијата двапати ќе пресметува кој е (N=4)тиот фибоначиев број, без да ги запамети резултатите. Слично, таа ќе продолжи да се повикува по неколку пати и за други вредности, како што е наведено на следната слика (тука функцијата се нарекува fib, за нејзиното име да не зафаќа непотребно многу простор на сликата).

Иако оваа слика прикажува само 15 повици на функцијата, тоа е така бидејќи бараме истата да го пресмета само 6-тиот фибоначиев број. За поголеми вредности на N, некои резултати ќе се пресметуваат и по стотици и илјадници пати, и функцијата ќе работи исклучително бавно. На пример, за откривање на 50-тиот фибоначиев број, на алгоритамот даден погоре ќе му требаат неколку минути да дојде до посакуваната вредност.

Едно решение на овој проблем е да искористиме дополнителна меморија за чување на вредностите (помалите состојби) кои веќе ги имаме пресметано. Во решението ќе искористиме мапа, но очигледно е дека можеме да искористиме и обична низа.

map<int, int> fib;
int fibonacci(int N)
{
     if (N == 1 || N == 2)
     {
          return 1;
     }
     
     //ako e vekje presmetan N-tiot, vrati go
     if(fib.count(N) > 0)
     {
          return fib[N];
     }
     
     //inaku, po presmetuvanjeto, zacuvaj ja vrednosta
     int value = fibonacci(N-1) + fibonacci(N-2);
     fib[N] = value;
     return value;
}

Нормално, овој код работи многу побрзо од претходниот, бидејќи истиот не анализира едни исти состојби по повеќе пати. Доколку ве интересира, конкретниот термин кој се користи за означување на оваа постапка е “мемоизација” (без р), и истиот означува дека ги чуваме резултатите на одредени функциски повици, и го враќаме тој (зачуван) резултат кога функцијата ќе се повика со истите аргументи (нормално, наместо истите повторно да ги пресметуваме).

Покрај ова, можеме и да почнеме да го разгледуваме проблемот од другата страна. Имено, доколку ги знаеме сите фибоначиеви броеви, почнувајќи од првиот, па вториот, па третиот, и така натаму се до X-тиот, можеме да го најдеме и (X+1)виот фибоначиев број, бидејќи тој е збир на претходните два. Ова решение е исклучително едноставно.

int fibonacci(int N)
{
     int fib[1001];
     fib[1] = fib[2] = 1;
     
     for(int i=3; i <= N; i++)
     {
          fib[i] = fib[i-1] + fib[i-2];
     }
     
     return fib[N];
}

За откривање на следниот фибоначиев број не ни се потребни сите претходни фибоначиеви броеви туку само претходните два, па не ни мораме да користиме низа за чување на сите претходни броеви, туку доволни ни се само две променливи кои ќе ги чуваат претходните два броја. Ова е прикажано со следниот код.

int fibonacci(int N)
{
     int oneBefore = 1, twoBefore = 1;
     int currentFibonacci = 1;
     
     for(int i=3; i <= N; i++)
     {
          twoBefore = oneBefore;
          oneBefore = currentFibonacci;
          
          currentFibonacci = oneBefore + twoBefore;
     }
     
     return currentFibonacci;
}

Во ова решение, во променливата oneBefore ја чуваме вредноста на претходниот број, додека во twoBefore ја чуваме вредноста на бројот пред претходниот. Нормално, во секое извршување на for циклусот, потребно е да ги ажурираме овие вредности, бидејќи тие се различни за секој чекор.

По долгата дискусија и разгледувањето на неколку начини на пресметка на фибоначиевите броеви, конечно можеме да ги дефинираме и двата стандардни начини на решавање со техниката на динамичко програмирање:

Решавање одозгора-надолу: разгледување на поголемите состојби преку објаснување како тие произлегуваат од помалите. На пример, кај рекурзивното решение наведовме дека N-тиот фибоначиев број е збир од (N-1)-виот и (N-2)-риот. Функцијата понатаму ќе продолжи да се повикува и за се помали вредности, се додека не дојдеме до основната (тривијална) состојба, каде знаеме дека првите два фибоначиеви броеви се еднакви на 1.

Решавање одоздола-нагоре: почнувајќи со најмалите состојби, правиме пресметки и ги откриваме вредностите за се поголеми состојби. Кај примерот со фибоначиевите броеви, ова значи дека почнуваме со дефинирање дека првите два фибоначиеви броеви се еднакви на 1. Потоа, ја пресметуваме вредноста на третиот број собирајќи ги првите два. Слично, го откриваме четвртиот број, и така натаму, се додека не дојдеме до N-тиот.

И двата начина на решавање се валидни и се користат често. Зависно од проблемот, некогаш е полесно да се почне со негово решавање одоздола, а некогаш одозгора. Сепак, бидејќи кај решавањето одозгора-надолу често користиме рекурзија, можно е да постојат проблеми доколку функцијата треба да се повикува себеси многу пати, бидејќи и ова повикување одзема меморија од компјутерот. Поради тоа, препорачано е да се користи решавањето одоздола-нагоре.

За крај, забележете дека фибоначиевите броеви растат многу брзо, па бидејќи користиме целобројни променливи (int) за чување на вредностите, можеме точно да пресметуваме до 46-тиот фибоначиев број, бидејќи следните се поголеми од она што може да се чува во тој податочен тип. На пример, 300-тиот фибоначиев број е дури 222232244629420445529739893461909967206666939096499764990979600. Целта на овој пример е да видиме како динамичкото програмирање може да ни помогне при решавањето на разни проблеми, а не да навлегуваме во нивно чување и слично. Фибоначиевите броеви се едноставни за разбирање, па затоа истите ги одбравме како пример.

Враќање кусур

Кога зборувавме за алчните алгоритми, го анализиравме проблемот на враќање на кусур, и наведовме зошто тој не може да се реши (за разни комбинации од монети) со правење на алчни одлуки. Најпрвин, да се потсетиме на проблемот кој што сакаме да го решиме. Нека имаме неограничен број на монети со различни вредности (на пример, од 1, 2, 5, 7 и 10 денари), и нека сакаме да вратиме кусур од X денари. Проблемот што сакаме да го решиме е да откриеме со колку најмалку монети можеме да го вратиме овој кусур? На пример, за X=25 денари, можеме да искористиме 3 монети (од 10, 10 и 5 денари). За кусур од 14 денари, можеме да искористиме 2 монети од по 7 денари.

Во предавањето за алчните алгоритми, разгледувавме континуирано земање на најголемата монета која е сеуште помала од бараниот кусур - но, на пример, за 14 денари тој алгоритам не работи точно, бидејќи ќе почне со земање на монетата од 10 денари, по што ќе ни останат 4 денари за враќање, за што се потребни две дополнителни монети од по 2 денари. Со тоа, сме искористиле 3 монети за враќање на кусур, а како што видовме од примерот погоре, постои начин да се врати кусур со само две монети од по 7 денари (7+7=14).

Сега, да видиме како динамичкото програмирање може да ни помогне да го решиме овој проблем, на начин што секогаш точно ќе го пресметуваме бараниот одговор. Поконкретно, ќе забележиме дека, кај алчните алгоритми, правевме избор кој изгледа точно само во дадениот момент (без разгледување на сите можности), а со динамичкото програмирање ги анализираме сите потребни и важни состојби (по одреден редослед, на пример од најмала до најголема), и начините на премин помеѓу нив.

Како и кај претходните примери, да започнеме со идејата дека знаеме како да вратиме кусур за сите вредности помали од X. Прашањето сега е, како да пресметаме колку најмалку монети ни се потребни за да вратиме кусур од X денари. Притоа, за овој пример, нека претпоставиме дека разгледуваме монети од 1, 2, 5, 7 и 10 денари, и нека сакаме да вратиме кусур од 19 денари.

Ако веќе знаеме со колку монети да направиме кусур за било која вредност помала од X (19 денари), тогаш за враќање на кусур од X (19 денари) треба да ги разгледаме следниве ситуации: следната за враќање монета да е од 1 денар, од 2 денари, од 5 денари, од 7 денари, или од 10 денари. Тоа се сите можни монети. Притоа, доколку последната монета е од 1 денар, тогаш ни е важно колку монети се искористиле за враќање на кусур од (X-1=18) денари, бидејќи 18 денари + 1 денар е точно 19 денари. Доколку за враќање на кусур од 18 денари биле потребни 3 монети, тогаш за враќање на кусур од 19 денари (вклучувајќи ја и монетата од 1 денар) ќе ни требаат 4 (3+1) монети. Слично, доколку последната монета е од 2 денари, тогаш ни е важно колку монети се искористиле за враќање на кусур од (X-2=17) денари, бидејќи 17 денари + 2 денари е точно 19 денари. Доколку за кусур од 17 денари биле потребни 2 монети, тогаш за враќање на кусур од 19 денари (вклучувајќи ја и монетата од 2 денари) ќе искористиме 3 (2+1) монети. Оваа постапка ја повторуваме за сите можни монети, и паметиме кој е најдобриот избор - во овој проблем, тоа е минималниот број на монети кои ни се потребни за враќање на кусурот. Во овој случај, подобро е да искористиме монета од 2 денари, бидејќи на тој начин ќе искористиме само 3 монети за враќање на кусурот од 19 денари.

Како и кај другите проблеми кои ги разгледавме, овој алгоритам ќе го повториме за сите вредности до X денари (почнувајќи од најмалата вредност, па нагоре), иако не интересира само потребниот број на монети за кусур од X денари (во случајов, 19 денари). Имено, за да можеме да ја пресметаме бараната вредност, потребно ни е, во моментот кога ќе стигнеме до X, да знаеме колку монети се потребни за враќање и на другите (помали) вредности. Слично направивме и кај фибоначиевите броеви, каде, иако не интересираше само одреден фибоначиев број, за да го откриеме истиот ни беа потребни и претходните. Како основна или тривијална состојба, можеме да започнеме со фактот што, за враќање на кусур од 0 денари, се потребни 0 монети. Кај фибоначиевите броеви, основна состојба беа првите два фибоначиеви броеви. Конечно, да го разгледаме решението на проблемот на враќање на кусур со најмал можен број на монети.

//koristi C++11 - http://mendo.mk/Lecture.do?id=26

int minimumCoins(vector<int> coins, int X)
{
     //dp[i] go sodrzhi minimalniot broj na
     //moneti koi se potrebni za dostiganje na vrednost "i"
     int dp[X+1];
     dp[0] = 0;
     
     for (int amount=1; amount<=X; amount++)
     {
          //pochni so nekoj golem broj za oznacuvanje deka nemame reshenie
          dp[amount] = 1000000000;
          
          //isprobaj ja sekoja moneta, i proveri dali e taa najdobar izbor
          for(int coinValue : coins)
          {
               if(coinValue > amount)
               {
                    //monetata e pregolema i ne mozhe da ja iskoristime za "amount"
                    continue;
               }
               
               int from = (amount - coinValue);
               
               //mozheme da zememe "1" moneta so vrednost "coinValue"
               //koja kje ne dovede od "from" do "amount"
               dp[amount] = min(dp[amount], dp[from] + 1);
          }
     }
     
     return dp[X];
}

Забележете дека одредени вредности (како, на пример, 2), доколку имаме соодветна монета со истата таа вредност (од 2 денари), ќе се пресметаат точно - како преоѓање од состојбата 0 до таа состојба (2), со земање на самата монета. Тоа придонесува за нашиот код да е толку краток и едноставен - без непотребно да ги разгледуваме како посебни случаи враќањето на првата монета, и останатите.

Временската сложеност на ова решение е O(X*C), каде со C е означен бројот на различни монети. Притоа, ова лесно може да се открие со преглед на самиот изворен код, каде имаме еден for циклус кој ги изминува сите можни вредности се до X (кусурот кој треба да се врати), и внатре во тој циклус се изминуваат сите монети.

Дополнително, важно е да наведеме дека оваа функција ќе врати резултат 1000000000 доколку кусурот не може да се врати со монетите кои ги имаме на располагање. Во самата функција, бројот 1000000000 е оној кој го имаме одбрано да ја претставува состојбата каде одредена вредност не може да се врати како кусур. Притоа, ова може да се случи, на пример, доколку имаме само монети од 5 и од 10 денари. Во ваков случај, не може да се врати кусур од 1 денар, од 7 денари, итн. Доколку постои монета од 1 денар, не постои кусур кој не може да се врати, бидејќи секогаш можеме да ги искористиме овие монети за враќање на кусурот.

Дозвола за користење: CC BY-NC 2.5 ©