introduction Of greedy algorithm with example

In an algorithm design, there's no band aid to all or any computational problems. Different problems require the utilization of various sorts of techniques. an honest programmer uses all of those techniques counting on the sort of problem. Some commonly used techniques are:

•  Divide and conquer
•  Random algorithms
•  Greedy algorithms (It's not an algorithm, it is a technique.)
•  Dynamic programming

Understand About “greedy algorithm”?

A greedy algorithm, because the name suggests, always makes the selection that seems to be the simplest at that point . this suggests that he makes a locally optimal choice within the hope that this choice will cause a globally optimal solution.

How does one decide which choice is optimal?

Suppose you've got an objective function that must be optimized (maximized or minimized) at some point. A Greedy algorithm makes greedy choices at every step to make sure that the target function is optimized. The Greedy algorithm only has one move to calculate the optimal solution in order that it never goes back and reverses the choice .

advantages and disadvantages for Greedy algorithms With Example:

•  It's pretty easy to seek out a Greedy algorithm (or even multiple greedy algorithms) for a drag .

•  time period analysis for greedy algorithms will generally be much easier than for other techniques (like Divide and conquer). For the Divide and Conquer technique, it's not clear whether the technique is fast or slow. Indeed, at each level of recursion, the dimensions of becomes smaller and therefore the number of sub-problems increases.

•  The hard part is that for greedy algorithms you've got to work tons harder to figure out the accuracy issues. Even with the proper algorithm, it's hard to prove why it's correct. Proving that a greedy algorithm is correct is more of an art than a science. It involves tons of creativity.

Note: Most of the greedy algorithms in DAA(data structure and algorithm) aren't correct. An example is described later during this article.

Greedy Algorithm Example

Greedy Algorithm Example

• First Make a empty set solution-set = { }.
  

• Coins 5,2,1
  

• sum = 0
  

• While sum ≠ 28, do the rest.
  

• Select a coin C from coins so that sum + C < 28.
  

• If C + sum > 28, return a empty solution.

• Else, sum = sum + C.

• Add C to solution-set.
  

Up to the primary 5 iterations, the answer set contains 5 $5 coins. then , we get 1 $2 coin and eventually , 1 $1 coin.

Where to use Greedy algorithms?

A problem must comprise these two components for a greedy algorithm to work:

 it's optimal substructures. The optimal solution for the matter contains optimal solutions to the sub-problems.

 it's a greedy property (hard to prove its correctness!). If you create a choice that seems the simplest at the instant and solve the remaining sub-problems later, you continue to reach an optimal solution. you'll never need to reconsider your earlier choices.