problem answer please

[Anna777]

Assume that there is a row of n coins whose values are some positive integers V1, V2, ...Vn. The coins may or may not be identical. We want to pick up the maximum amount of money. However, we cannot pick up two adjacent coins. Write a recursive program that takes input from the user and display the maximum amount of money that can be picked up from the row of n coins. The program should also display the coins that are selected to get the maximum amount of money.

ex)
enter the number of coins: 6
enter the value of all coins : 5 1 2 10 6 2

The maximum amount of coin : 17
The selected coins to get maximum value : C1 , C4 , C6

[Yokana]

@Anna777

The program should also display the coins that are selected to get the maximum amount of money.

Did you implement this part of the assignment?

[Anna777]

No, I have no idea with solving this problem.. sadly...
I have to figure this out with recursive function... help me...

[ne555]

Think on the base cases.
If you've got no coins, the answer is 0.
If you've got one coin, take it.
If you've got two coins, you need to consider to take the first one or the second one.

Then you do the inductive step.
Suppose that you do know how to solve the problem for `n' coins, ¿how may you take that knowledge to solve it for `n+1' coins?

[JLBorges]

function maximum_amout_of_money

    input array of integer values[] : values of coins
    input integer from: position of the first coin that can be picked
    input integer to: position of the lastst coin that can be picked
    result: maximum amount of money that can be picked
    
    let integer n = to - from + 1 (number of coins)
    
    if there are no coins ( n<1 ) : return zero 
        
    if there is only one coin ( n==1 ) : return the value of that coin values[from]
    
    else if there are two coins ( n==2 ) : return the larger of the two values values[from] and values[to]
        
    else ( n>2 ) : return maximum of 
        a. values[from] + maximum_amout_of_money( values, from+2, to ) - try picking the first coin 
        b. values[ from+1 ] + maximum_amout_of_money( values, from+3, to ) - try picking the second coin 

Take it up from there.