AG
1:25 AM X * l.l 12%
DAA UNIT-IV (jntu... D
www.android. niversirvupdates. in wWw.wniersirvupdates. in hups:/telegram.me jntuh
UNIT II:
Greedy method: General method, applications - Job sequencing with deadlines, 0/1
knapsack problem, Minimum cost spanning trees, Single source shortest path problem.
Dynamic Programming: General method, applications-Matrix chain multiplication, Optimal
binary search trees, O/1l knapsack problem, All pairs shortest path problem, Travelling sales
person problem, Reliability design.
Greedy Method:
The greedy method is perhaps (maybe or possible) the most straight forward design
technique, used to determine a feasible solution that may or may not be optimal.
Feasible solution:- Most problems have n inputs and its solution contains a subset of inputs
that satisfies a given constraint(condition). Any subset that satisfies the constraint is called
feasible solution.
Optimal solution: To find a feasible solution that either maximizes or minimizes a given
objective function. A feasible solution that does this is called optimal solution.
The greedy method suggests that an algorithm works in stages, considering one input at a
time. At each stage, a decision is made regarding whether a particular input is in an optimal
solution.
Greedy algorithms neither postpone nor revise the decisions (ie., no back tracking).
Example: Kruskal's minimal spanning tree. Select an edge from a sorted list, check, decide,
and never visit it again.
Application of Greedy Method:
> Job sequencing with deadline
> 0/1 knapsack problem
Minimum cost spanning trees
> Single source shortest path problem.
|Algorithm for Greedy method
Algorithm Greedy(a,n)
la[ l:n] contains then inputs.
Solution :=0;
For i=l to n do
| X:=select(a);
If Feasible(solution, x) then
Solution :=Union(solution,x):
Return solution:
Selection > Function, that selects an input from a•] and removes it. The selected input's
value is assigned to x.
Feasible ’ Boolean-valued function that determines whether x can be included into the
solution vector.
Union > function that combines x with solution and updates the objective function.
DESIGN AND ANALYSIS OF ALGORITHMS Page 44
wWW.hdroid.previotSqitestionpapers.com wWw.previousquestiOHpapers.com htps:telegram. ne jitult
WWW.androd wniversityupdates.in wWw.tversitvupdates.in https:/telegram.me jntuh
Knapsack problem
The knapsack problem or rucksack (bag) problem is a problem in combinatorial optimization: Given a set of
items, each with a mass 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
$4 T12 ko ? L2
15 kg
$10TA KO
There are two versions of the problems
1. 0l knapsack problem
2. Fractional Knapsack problem
a. Bounded Knapsack problem.
b. Unbounded Knapsack problem.
