Benefits of Greedy Solutions

Generally, there are two Algorithmic paradigms for solving optimization problem as stated below

1)Dynamic Programming
2)Greedy Algorithm.

A greedy algorithm is an algorithmic strategy in which we make the locally optimal choices at each stage in the hope of finding the global optimal solution. In many problems, a greedy strategy may not always produce an optimal solution, but nonetheless, a greedy approach may sometimes yield locally optimal solutions that approximate a globally optimal solution in a reasonable amount of time but unlike dynamic programming, greedy does not apply to all optimization problems.

There is the numerous number of the algorithm that is being developed using greedy approach some of them are as under that are being used in real time.

1)Minimum spanning tree. (Mostly used in computer or road network to find minimum no of cost for traversing all the node or cities in the graph).
 
 Greedy Algorithm available
       1)Prims Algorithm

       2)Kruskal Algorithm

2)Fractional Knapsack problem.

3)Huffman codes used in data compression in the most famous data compression tool.

4)Job sequencing with deadlines.

5)Optimal Merge Pattern.

It would be easy to understand the working of them through some code. Suppose you are creating a utility in An Exchange
where the user needs to find out how much profit he/she could have made my selling single coin in last day so as to maximize his/her profit. Sound interesting.....

Here is simple Optimize greedy Implementation for the above problem.

import java.util.Scanner;
 
public class ExchangeCoinToMaximizeProfit {
	
	
	
	/**
	 * Some time being greedy can be profitable, here i am greedy about 
	 * trade.
	 * @param priceList
	 * @return
	 */
	static long calulateMaxProfit(long priceList[]){
		long CBA=priceList[0];
		long totalProfit=0L;
		for(int i=1;i<priceList.length;i++){
			
			if(priceList[i]<CBA){
				CBA=priceList[i];
			}else if(priceList[i]>CBA){
				totalProfit+=priceList[i]-CBA;
				CBA=priceList[i];
			}
		}
		return totalProfit;
		
	}
 
	public static void main(String args[]){
		Scanner sc=new Scanner(System.in);
		String input[]=sc.nextLine().split(" ");
		long n=Long.parseLong(input[0]);
		long m=Long.parseLong(input[1]);
		input=sc.nextLine().split(" ");
		long a=Long.parseLong(input[0]);
		long b=Long.parseLong(input[1]);
		long c[]=new long[(int)n];
		long x[]=new long[(int)n+1];
		long base=(long)Math.pow(2.0, 32.0);
		long divide=(long)Math.pow(2.0, 8.0);
		for (int i = 0; i < n; i++) {
			x[i+1] = (x[i] % m * a + b) % base;
		    c[i]=(long)Math.floor(x[i+1]/256.0);
		}	
		System.out.println(calulateMaxProfit(c));
	}
 
}

Hope it is helpful to someone.