/////////////////////////////////////////////////////////////////////////////////////////////////////////////
DYNAMIC ALGORITHM?
The given problem is looked like the extension of a small problem.
Then, solve the problem recursively by using the values of solution of small problem.
When each small problem is not independent of others and necessary to take advantage of their sub-problem back, Dynamic algorithm can be applied.
Example
{ 1 }
Knapsack Problem
In Dynamic Algorithm, make a table for solving knapsack problem.
-
Row is the index of item.
(example of 2, we use item 1, item 2)
Column is weight that can be put. -
By combining well the items that have and weight that can be put, write highest value.
-
The last column is solution after all process is finished.
{ 0 }
Other algorithms
-
Warshall's Algorithm
-
Floyd's Algorithm
Warshall's Algorithm
GROUP PROJECT
////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
Important Activity
Within a predetermined time, a program output the list which process as possible works have the highest priority.
-
Input value: time remaining until the school, the name of the work, running time, severity
-
It is similar with Knapsack's principle.
Higher importance within a given time is to be selected. -
Print both the name and the time and severity that is selected.
What steps does dynamic algorithm have?
Compute the value of the optimal solution from small problem to big problem
Look for the structure of the optimal solution
Define the
value of the optimal solution recursively.
Find the value
of the optimal solution by utilizing the information obtained above
What are the advantages and disadvantages?
When implementing the program, can be implemented by considering all possibilities required. Therefore, it is possible to obtain always best results.
But, if examination of all possibilities is insufficient, you will not be able to guarantee optimal results. And, it oftens requires more memory than other algorithms.
Also, it can take a long time when the input value increases because it uses a recursive function.
SOLUTION