How do I solve the Coin Row problem using dynamic programming?

0
votes

Coin-row problem: There is a row of n coins whose values are some positive integers C0, C2, . . . , Cn-1, 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.

In the below code, n is the size of my array C(or number of coins), and this code returned the right result for the values [10, 2, 4, 6, 3, 9, 5] (the right result being 25). But when I run the same code for the values [3, 12, 10] or [3, 12, 10, 2], I got the wrong result. (The result should be 13 and 14 respectively for the set of values).

Please help me fix my code.

int max(int a, int b) {
  if(a > b) return a;
  return b;
}

int coin_row(int[] C, int n) {
  if(n==1) return C[0];
  if(n==2) return max(C[0],C[1];

  int F[n], i;
  F[0] = 0; F[1] = C[0];

  for(i = 2;i < n;i++) {
    F[i] = max(C[i] + F[i-2], F[i-1]);
  }

  return F[n-1];
}
2
calgorithmdynamic-programming
What F stands for? If F[i] is maximum amount of money you can take using only first i+1 coins, then F[0] = 0; F[1] = C[0]; should be replaced with F[0] = C[0]; F[1] = max(C[0], C[1]); just like in cases when n is 1 or 2. – fas

2 Answers

2
votes

The statement that all numbers will be positive makes things a little easier. From that information we can determine that we never want to skip over two consecutive numbers. We just have to calculate the best sequence possible using the first number and compare it with the best sequence possible using the 2nd number. This is ideal for recursion.

int coin_row(int *C, int n) 
{
    int first_total;
    int second_total;

    if (n == 0) return 0;
    if (n == 1) return *C;
    if (n == 2) return max(*C, *(C+1));

    first_total = *C + coin_row(C+2, n-2);
    second_total = *(C+1) + coin_row(C+3, n-3);
    return(max(first_total, second_total));
}

By breaking down the problem into a sequence of pairs we treat the list as a large binary tree. At every pair you can choose either the first or second number. Calculate the total for each sub-tree and return the greatest value. For example with {10, 2, 4, 6, 3, 9, 5} your paths are:

          10                    2
          /\                   /\
         4  6                 6  3
        /\  /\               /\  /\
       3  9 9 5             9  5 5 -
1
votes

Your algorithm is right but there are some bugs in implementation. You are skipping the value at C[1] as your loop starts from i=2. Since you are including 0 coin case in your F array, it needs to be of size n+1 for F[n] to exist. With the above corrections we arrive at:

int max(int a, int b) {
  if(a > b) return a;
  return b;
}

int coin_row(int* C, int n) {
  if(n==1) return C[0];
  if(n==2) return max(C[0],C[1]);

  int F[n+1], i;
  F[0] = 0; F[1] = C[0];

  for(i = 2 ; i <= n + 1 ; i++) {
    F[i] = max(C[i-1] + F[i-2], F[i-1]);
  }
  return F[n];
}