EXAMPLE 1 Coin-rowproblem There is a row of n coins whose values are some positi
ID: 3641637 • Letter: E
Question
EXAMPLE 1 Coin-rowproblem There is a row of n coins whose values are somepositive integers c1, c2, . . . , cn, not necessarily distinct. The goal is to pick up the
maximum amount of money subject to the constraint that no two coins adjacent
in the initial row can be picked up.
Let F(n) be the maximum amount that can be picked up from the row of n
coins. To derive a recurrence for F(n), we partition all the allowed coin selections
into two groups: those that include the last coin and those without it. The largest
amount we can get from the first group is equal to cn
+ F(n - 2)—the value of the
nth coin plus the maximum amount we can pick up from the first n - 2 coins. The
maximum amount we can get from the second group is equal to F(n - 1) by the
definition of F(n). Thus, we have the following recurrence subject to the obvious
initial conditions:
F(n) = max{cn
+ F(n - 2), F(n - 1)} for n > 1,
F(0) = 0, F(1) = c1.
(8.3)
We can compute F(n) by filling the one-row table left to right in the manner
similar to the way it was done for the nth Fibonacci number by Algorithm Fib(n)
in Section 2.5.
ALGORITHM CoinRow(C[1..n])
//Applies formula (8.3) bottom up to find the maximum amount of money
//that can be picked up from a coin row without picking two adjacent coins
//Input: Array C[1..n] of positive integers indicating the coin values
//Output: The maximum amount of money that can be picked up
F[0]?0; F[1]?C[1]
for i ?2 to n do
F[i]?max(C[i]+ F[i - 2], F[i - 1])
return F[n]
Solve the instance 5, 1, 2, 10, 6 of the coin-row problem.
Explanation / Answer
The answer is literally in the examples. Just ignore the whole last chart for f(6) and the last column of the preceding 5 charts.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.