coin-row problem: there is a row of n coins whose values are some positive inter
ID: 3675415 • Letter: C
Question
coin-row problem: there is a row of n coins whose values are some positive intergers c1, c2, c3, not neccessarily distinct, the goal is to pick up the maximum a let F(n) be the maximum amount of money subject to the constraint that no two coins adjacent in the initial row can be picked up.
(1) let F(n) be the maximum amount that can be picked up from the row of n coins. please derive a recurrence for computing F(n)
(2) apply the dynamic programming algorithm to solve instance 6, 5, 3, 10, 8 of coin-row problem. (Note: you need to compute F(0), F(1) ..., F(5) in that order)
Explanation / Answer
Let A be the given array and Sum be another array such that Sum[i] represents the maximum sum of non-consecutive elements from arr[0]..arr[i].
We have:
Sum[0] = arr[0]
Sum[1] = max(Sum[0],arr[1])
Sum[2] = max(Sum[0]+arr[2],Sum[1])
...
Sum[i] = max(Sum[i-2]+arr[i],Sum[i-1]) when i>=2
If size is the number of elements in arr then sum[size-1] will be the answer.
1).
One can code a simple recursive method in top down order as:
int sumMax(int *arr,int i) {
if(i==0) {
return arr[0];
}else if(i==1) {
return max(arr[0],arr[1]);
}
return max(sumMax(arr,i-2)+arr[i],sumMax(arr,i-1));
}
2).
The above code is very inefficient as it makes exhaustive duplicate recursive calls. To avoid this we use memoization by using an auxiliary array called sum as:
int sumMax(int *arr,int N) {
int *F = malloc(sizeof(int) * N);
int i;
for(i=0;i<N;i++) {
if(i==0) {
F[0] = arr[0];
}else if(i==1) {
F[1] = max(F[0],arr[1]);
}else{
F[i] = max(F[i-2]+arr[i],F[i-1]);
}
}
return F[N-1];
}
Which is O(N) in both space and time.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.