Consider the following generalization of the Activity Selection Problem: You are given a
set of n activities each with a start time si, a finish time fi, and a weight wi. Design a
dynamic programming algorithm to find the weight of a set of non-conflicting activities
with maximum weight. - ANSWE...
consider the following generalization of the activ
Geschreven voor
Alg quz
Alg quz
Verkoper
Volgen
AnswersCOM
Ontvangen beoordelingen
Voorbeeld van de inhoud
alg
quiz
Consider
the
following
generalization
of
the
Activity
Selection
Problem:
You
are
given
a
set
of
n
activities
each
with
a
start
time
si,
a
finish
time
fi,
and
a
weight
wi.
Design
a
dynamic
programming
algorithm
to
find
the
weight
of
a
set
of
non-conflicting
activities
with
maximum
weight.
-
ANSWER-Formula:
(Sort
by
finish
time)
A[i]
=
max
(from
activity
1
to
i)
{
A[i
-
1]
max{A[x]}
+
wi
}
(x
being
activity
whose
finish
time
<=
activity
i's
start
time)
A
contiguous
subsequence
of
a
list
S
is
a
subsequence
made
up
of
consecutive
elements
of
S.
For
instance,
if
S
=
{5,
15,
−30,
10,
−5,
40,
10}
then
{15,
−30,
10}
is
a
contiguous
subsequence
but
{5,
15,
40}
is
not.
Give
a
dynamic
programming
algorithm
for
the
following
task:
You
are
given
a
list
of
numbers,
{a1,
a2,
.
.
.
,
an}.
You
should
return
the
contiguous
subsequence
of
maximum
sum
(a
subsequence
of
length
zero
has
sum
zero).
For
the
preceding
example,
the
answer
would
be
10,
−5,
40,
10,
with
a
sum
of
55.
-
ANSWER-Formula:
CSH[i]
=
max{
0
CSH[i
-
1]
+
Vi
}
You
are
going
on
a
long
trip.
You
start
on
the
road
at
mile
post
0.
Along
the
way
there
are
n
hotels,
at
mile
posts
a1
<
a2
<
·
·
·
<
an,
where
each
ai
is
measured
from
the
starting
point.
The
only
places
you
are
allowed
to
stop
are
at
these
hotels,
but
you
can
choose
which
of
the
hotels
you
stop
at.
You
must
stop
at
the
final
hotel
(at
distance
an),
which
is
your
destination.
You
would
ideally
like
to
travel
300
miles
a
day,
but
this
may
not
be
possible
(depending
on
the
spacing
of
the
hotels).
If
you
travel
x
miles
during
a
day,
the
penalty
for
that
day
is
(300
−
x)^2.
You
want
to
plan
your
trip
so
as
to
minimize
the
total
penalty-that
is,
the
sum,
over
all
travel
days,
of
the
daily
penalties.
Give
a
dynamic
programming
algorithm
to
determine
the
optimal
sequence
of
hotels
at
which
to
stop.
-
ANSWER-Formula:
P[i]
=
min
(0
<=
k
<=
i)
{
Voordelen van het kopen van samenvattingen bij Stuvia op een rij:
Verzekerd van kwaliteit door reviews
Stuvia-klanten hebben meer dan 700.000 samenvattingen beoordeeld. Zo weet je zeker dat je de beste documenten koopt!
Snel en makkelijk kopen
Je betaalt supersnel en eenmalig met iDeal, creditcard of Stuvia-tegoed voor de samenvatting. Zonder lidmaatschap.
Focus op de essentie
Samenvattingen worden geschreven voor en door anderen. Daarom zijn de samenvattingen altijd betrouwbaar en actueel. Zo kom je snel tot de kern!
Veelgestelde vragen
Wat krijg ik als ik dit document koop?
Je krijgt een PDF, die direct beschikbaar is na je aankoop. Het gekochte document is altijd, overal en oneindig toegankelijk via je profiel.
Tevredenheidsgarantie: hoe werkt dat?
Onze tevredenheidsgarantie zorgt ervoor dat je altijd een studiedocument vindt dat goed bij je past. Je vult een formulier in en onze klantenservice regelt de rest.
Van wie koop ik deze samenvatting?
Stuvia is een marktplaats, je koop dit document dus niet van ons, maar van verkoper AnswersCOM. Stuvia faciliteert de betaling aan de verkoper.
Zit ik meteen vast aan een abonnement?
Nee, je koopt alleen deze samenvatting voor €7,80. Je zit daarna nergens aan vast.
