[go: up one dir, main page]

0% found this document useful (0 votes)
12 views29 pages

Greedy Method 02 Class Notes.pdf

Uploaded by

Teerth Bhardwaj
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
0% found this document useful (0 votes)
12 views29 pages

Greedy Method 02 Class Notes.pdf

Uploaded by

Teerth Bhardwaj
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 29

CS & IT 20 25

ENGINEERING
Algorithms

Greedy Method

Lecture No.- 02 By- Aditya sir


Recap of Previous Lecture

Topic
Greedy

Topic
Fractional Knapsack

Fonts
examples
Topics to be Covered

Topic Fran apsancontinued


Topic Terminologies

Job scheduling

3
FIDknapsack
HI
n 7

If
10
want
2

3
02
15 5
03
04 7

05 6

06 18 4
I
3
OF
4
0060
1
5
11
45 30

3 40

3 50
A

X
1_ e D
On Ew 1
6
V.EE
5
mj
M E ˢ Optimal Maximum Profit
M 15 1 16

m 14 2 12 1 1 XIAP
8 15
18 3
M 8 1 7 1 1
0 7
0
54
M 7 5
2 3 1

2117
2 2 0
M 2 16 18 18
0
4

524 3 33
Irational
rival ans

BE
feed

13
Topic : Greedy Techniques
Fractionalknapsack­
Procedure GREDY_KNAPSACK(P, W, M, X, n)
// P(1 : n) and W(1 : n) contain the profites and weights respectively of the n//
// knapsack size and X(1 : n) is the solution vector//
0brarranged as per
Pfwivalue
Real P(1 : m), W(I : n), X (1 : n), M cu;
integer I, n;
I.IT decreasing
x ← 0 // initialize solution to zero//
cu ← M // cu = remaining knapsack capacity//
I 2_ Xn
for i ← 1 to n do o o o 0

if W(i) > cu then exit endif


seen
X(i) ← 1
cu ← cu –W(i)
highest_Lowest
Plw
w
Repeat
if i ≤ n then X(i) ← (cu/W(i))endif
name
if objects are
end GREEDY–KNAPSACK
remaining
Topic : Greedy Techniques V V V
IMP PYS

#Q.Consider the weights and values of items listed below. Note that there is only one
unit of each item.

item number
item number Weight
Weight (ininky
kg) Value
value (inin Rupees)
Rs
11 1010 60
60
2 7 28
33 44 20
44 22 24
24C
Ed.si
Topic : Greedy Techniques
5 meff

#Q.The task is to pick a subset of these items such that their total weight is no more

E
than 11 kgs and their total value is maximized. Moreover, no item may be split. The

f
R
total value of items picked by an optimal algorithm is dented by V . A
algorithm sorts the items by their value-to-weight ratios in descending
opt
greedy
order and

1 items picked by the greedy algorithm is denoted by V f


packs them greedily, starting from the first item in the ordered lits. The total value of

greedy
. The value of V opt
– Vgreedy

6
is _____.

word Ami 60
I opt
M
1
If KPI
Possibilities

5 P Ps 48
1 PB

7 PB Pu ay
24

opt

13
Part on 6
II

BE
5 11 greedy
If

13
M 1

o i i

M 1 0
Profit gaudy
4 1 M 11 2 9 approach
X 1079 1
0 skip Hedy
IX
Put XP
M 9 4 5 43 1 1 13 0 12
5 7
1
M 0
13 2 24 0 20 0 1447
Our all ans opt Vgundy
60 44

I
Imps 1 0 Binary knapsack

Vopt 60

Pw apps gaudy

13
freemently used
IMPTermino
logi.fi
ProblemDefinition
Instantly
Solution Space
Input Explician
i
ffdfdxplicit
constraints
f
Boundary
Feaseablesolution a
Solution Space
those Solutions from
constraints
that also satisfies Pmdd
13
Examine GueensProbleme
N
It them
n Queens on a nxn board arrange
Given
That no twofeens attack each other

eq.in or or or org I
q

1 n 92

Viin the g
fits position of
i throw
94
13 1 xi n
y n g

1,2 3,4 sizeofsolutionspaee­x

4 si

4,3 2,1
r

13
a x 1,3
92 q
x x x x
q
easeable
94 c son

13
or
a
92
92 92
0
93 9 9 93
94
94
Soln Size
12.4.13 4 1344,2 I
has 41 21
eai Solution
aveenfwf.in feaseable
4
13
Hassle
Objectivfundione
Optional
maximize a
minimise
Tries to Ise
criteria the problem
given of

og Knapsay Maximize Profit

13
eIpath Minimise path lost
Optimalsolulfo.fi
It is that feaseabite
Soln that satisfies
the
objectiffunition
to the
ftp.QOPIlntionfoaydeis refers
value
d
and hence it unique
Shortest

eg A BY A C

A B C
D 5 7 12
min lost A C

A D C 8 4
12
13 II
9 what is the
objection function
feaseable
of n Queens
problem be
can

It does not
how TÉLÉmany

objective function
any
Soln
Hence no optimal optimal
Soln

It does have multiple fuel


13
forseable Ions
mnanPobi
In
ask.IT
False
revives
min max
to detain
value optimal
either True
criteria
Yes No 1 0
of a
given
not
feassable Sets max
objective function
011 Profit
eg Searching
knapsack Frational
Sorting
min
Shortest path Problems
etc cost
n Queens
13
Problems Jots Sequencing deadline JSD

fewsimilarocuschedulingProblems

Given
a single CPU Normplifcheduling

given
n
jobs IProiesse.se

13
Desiription Tobi
III
f

Profit
Enoybi Arrival
time
Bu
of
AT
Lodged
Innit

13
Problem
statement
that
s Select a subset of n'given jobs such

completed within
all the in the subset are
jobs
and generate
deadlines
this corresponding

the maximum.PH 1obje tin

Completed within the


the Job gets
Note Only when the
deadline then only you get
given else not
associated profit
13
n
Deadline
profit 5 0
51 200 2

52 30

53 50 2
DIII
or
54
80 I
2004 on
30

50 80

13
3 151 2
b C

a
ME 200 30
1 Profit
4 2 50 80
Profit
nota
feast
E
d e
y Top
50 200
Profit 200

optinff
teaseable
13
is Brute Force Enumeration
This approach

list of Soln space

0 2n

Hence not a good idea Fte this

based approach
we need a
Yundy Algorithm

13
THANK - YOU

Telegram Link for Aditya Jain sir:


https://t.me/AdityaSir_PW

14

You might also like