Coding_wolrd
Greedy Algorithm Introduction
"Greedy Method finds out of many options, but you have to choose the best option." In this method, we have to find out the best method/option out of many present ways. In this approach/method we focus on the first stage and decide the output, don't think about the future. This method may or may not give the best output.
What is Greedy Algorithm?
Greedy Algorithm solves problems by making the best choice that seems best at the particular moment. Many optimization problems can be determined using a greedy algorithm. Some issues have no efficient solution, but a greedy algorithm may provide a solution that is close to optimal
Why study Greedy Algorithm?
It is solving a optimization problem . A soluation to satify solution of the given problem is know as feasible soluation.
Greedy method use to solving optimization problem
Properties of Greedy Algorithms
- Greedy Choice Property:A globally optimal solution can be reached at by creating a locally optimal solution.
- Optimal substructure: Optimal solutions contain optimal subsolutions. In other words, answers to subproblems of an optimal solution are optimal.
Advantages of an Greedy Algorithm
- Feasible: we check whether it satisfies all possible constraints or not, to obtain at least one solution to our problems.
- Unalterable:Once the decision is made, at any subsequence step that option is not altered.
- Local Optimal Choice: the choice should be the optimum which is selected from the currently available
Example of Greedy Algorithm
- 1. machine scheduling
- 2. Fractional Knapsack Problem
- 3. Minimum Spanning Tree
- 4. Huffman Code
- 5. Job Sequencing
- 6. Activity Selection Problem
How to write algorithm
- Algo Greedy(a,n)
- {
- for i=1 to n
- x=select(a)
- if feasible (x) then
- solation=soluation+x
- }
Note:
1.Min cost + feasible soluation ==> optimal soluation
Knapsack problem
What is Knapsack_problem?
The knapsack problem is a problem in combinatorial optimization: Given a set of items, each with a weight and a value, determine the number of each item to include in a collection so that the total weight is less than or equal to a given limit and the total value is as large as possible
I found the Knapsack problem tricky and interesting at the same time. I am sure if you are visiting this page, you already know the problem statement but just for the sake of completion :
The Greedy algorithm could be understood very well with a well-known problem referred to as Knapsack problem. Although the same problem could be solved by employing other algorithmic approaches, Greedy approach solves Fractional Knapsack problem reasonably in a good time. Let us discuss the Knapsack problem in detail.
How to write algorithm
- for i=1 to n
- calculate p/w
- sort obj in descending oder of p/w ratio
- for i=1 to n
- if m > 0 and w < m
- m=m-wi;
- p=p+pi;
- else
- if(m>0)
- p=p+pi(m/wi)
No comments:
Post a Comment