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...
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)
{
The benefits of buying summaries with Stuvia:
Guaranteed quality through customer reviews
Stuvia customers have reviewed more than 700,000 summaries. This how you know that you are buying the best documents.
Quick and easy check-out
You can quickly pay through credit card or Stuvia-credit for the summaries. There is no membership needed.
Focus on what matters
Your fellow students write the study notes themselves, which is why the documents are always reliable and up-to-date. This ensures you quickly get to the core!
Frequently asked questions
What do I get when I buy this document?
You get a PDF, available immediately after your purchase. The purchased document is accessible anytime, anywhere and indefinitely through your profile.
Satisfaction guarantee: how does it work?
Our satisfaction guarantee ensures that you always find a study document that suits you well. You fill out a form, and our customer service team takes care of the rest.
Who am I buying these notes from?
Stuvia is a marketplace, so you are not buying this document from us, but from seller AnswersCOM. Stuvia facilitates payment to the seller.
Will I be stuck with a subscription?
No, you only buy these notes for $7.99. You're not tied to anything after your purchase.
