Question
Solve the instance 5, 1, 2, 10, 6 of the coin-row problem.
Answer
Procedure : 1) There is a row of n coins whose values are some positive integers C1,C2,C3,.....Cn not necessarly distinct
2) The objective is to pick up the Maximum amount of money subject to the constraint that no two coins adjacent in the intial row can be picked up
3) To find F(n)= Max{Cn+F[n-2],F[n-1]} for all n>1, where F[0]=0 and F[1]= C1
input Array : C[1,2,3,4,.......] of positive intigers indicating the coin values
Output Array: The maximum amount of money that can be picked up
| Index | 0 | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|---|
| Coin (C) | 0 | 5 | 1 | 2 | 10 | 6 |
| F values for every loop ( F) | 0 | 5 | 5 | 7 | 15 | 15 |
| History | C1 | - | C3 | C4 | - | |
| Maximum Value of Coins to be taken | F[1] | F[1] | F[2] | F[4] |
For calculating the F value we have to generate another table:
| F(Index) | Max Value |
| F[0] | 0 |
| F[1] | C1 = 5 |
| F[2] | Max(C2+F[0],F[1])=> Max(1+0,5)= 5 {We got this value From F[1]} |
| F[3] | Max(C3+F[1],F[2])=> Max(2+5,5)= 7 {We got this value while adding C3 to F[1]} |
| F[4] | Max(C4+F[2],F[3])=> Max(10+5,7)= 15 {We got this value while adding C4 to F[2]} |
| F[5] | Max(C5+F[3],F[4])=> Max(6+7,15)= 15 {We got this value F[4]} |
From the Starting table we have calcutated that C1 and C4 are the coins will give maixmum value, C1 +C4 = 5+10 =15