IJCATR Volume 8 Issue 8

Comparative Study of Dynamic Programming and Greedy Method

San Lin Aung
10.7753/IJCATR0808.1007
keywords : Greedy Algorithm, Dynamic Programming, 0/1 Knapsack, Algorithm

PDF
This paper discusses relationships between two approaches to optimal solution to problems: Greedy algorithm and dynamic programming. Greedy algorithm has a local choice of the sub-problems whereas Dynamic programming would solve the all sub-problems and then select one that would lead to an optimal solution. Greedy algorithm takes decision in one time whereas Dynamic programming takes decision at every stage. This paper discuss about Dynamic Programming and Greedy Algorithm to solve the Knapsack Problem where one has to maximize the benefit of items in a knapsack without extending its capacity. The paper discusses the comparison of each algorithm in terms of time different Item values. The comparison result of two algorithms are described with the best local result produced by the algorithm against the real exact optimal result.
@artical{s882019ijcatr08081007,
Title = "Comparative Study of Dynamic Programming and Greedy Method",
Journal ="International Journal of Computer Applications Technology and Research(IJCATR)",
Volume = "8",
Issue ="8",
Pages ="327 - 330",
Year = "2019",
Authors ="San Lin Aung"}
  • .