Dinamičko programiranje ; Dynamic programming

Zadatak ovog rada bio je opisati i na konkretnom primjeru implementirati tehniku dinamičkog programiranja, Ovom tehnikom početni složeni problem rastavljamo na podprobleme manje složenosti koji su međusobno zavisni. Svaki podproblem se rješava najviše jednom, čime možemo izbjeći višestruko računanje numeričkih karakteristika istog stanja. Osnovna ideja na koju se oslanjaju algoritmi dinamičkog programiranja je da se svaki dobiveni međurezultat, odnosno rješenje podproblema, spremi te zatim kada se sljedeći puta naiđe na taj isti podproblem, izbjegne njegovo ponovno rješavanje. Ovakva tehnika pohrane rješenja podproblema naziva se memoizacija. Dva osnovna pristupa pomoću kojih možemo rješavati probleme dinamičkim programiranjem su: pristup „Odozgo prema dolje“ i pristup „Odozdo prema gore“. U glavnom dijelu rada navedeni pristupi su implementirani na primjeru „Rezanje drva“ te je izmjereno vrijeme izvođenja dobivenih funkcija. Na kraju smo zaključili da problem riješen ovom tehnikom ima znatno brže vrijeme izvođenja od onog riješenog nedinamičkom metodom ; The task of this paper was to describe a dynamic programming technique and then implement solution for specific problem. Using this technique, we break down the initial complex problem into a collection of simpler subproblems. Each subproblem is solved once and its solution had been stored. The next time the same subproblem occurs, instead of recomputing its solution, one simply looks up the previously computed solution. The technique of storing solutions to subproblems instead of recomputing them is called "memoization". There are two ways of doing this: with Top-down approach and with Bottom-up approach. In the main part of this paper these approaches were implemented in the example "Rod cutting" and the time taken to perform the obtained functions was measured. In the end, we have concluded that the problem solved by this technique has much faster execution time than one solved with other method.