Greedy Method (Laboratory Component)

 greedy means desire for food or wealth in generic.

Grredy method is algorithm design technique.

It helps to solve optimization problems like coin change problem (minimize number of coins to be used) , to find shortest paths, knapsack problem and job sequencing, etc.

General Plan:

1. Feasible

2.Locally optimal

3.Irrevocable

Knapsack Problem (Greedy Technique to solve it) (Fractional Knapsack)

knapsack=bag or bagpack

Aim:

Pack or carry n objects of different weights and price into a bag to maximize the profit.

Let us assume:

n objects we have

Wi weigth of each object

Pi price of each object

Select fraction of objects that must be

0<=xi<=1

xi  Fraction of ibject like 1/2 1/3 2/3, etc.

0 means we do not select object

1 means we select the entire object