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)
{
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)
{
