Coins of different denominations are placed one after the other, pick coins to maximize the sum

Question

Coins of different denominations are placed one after the other. You need to pick coins one by one (except first and last) until there are only 2 coins (first and the last) left. Each time you pick a coin you multiply it's left and right coins values. The problem is to pick coins in such an order so that the sum of all the multiplications is maximum. For example:

let say coins are placed as 1, 6, 7, 4

There are 2 ways to pick coins:

First way: first pick 6, this will result in 1*7 = 7 and then pick 7, this will result in 1*4 = 4, so total would be 7 + 4 = 11

Second way: first pick 7, this will result in 6*4 = 24 and then pick 6, this will result in 1*4 = 4, so total would be 24 + 4 = 28

As 28 is largest, that's our answer.

I could find the right answer by recursively traversing through all the possible cases and comparing their output values but this solution is very inefficient as it takes exponential time. Please let know how can this problem be solved more efficiently.

EDIT : The recursive solution

int remove (int a [], int end, int pos) {
    int tmp = a[pos];
    for (int i = pos + 1; i <= end; i++) {
        a[i - 1] = a[i];
    } a[end] = 0;
    return tmp;
}

int * insert (int a [], int end, int pos, int val) {
    for (int i = end; i >= pos; i--) {
        a[i + 1] = a[i];
    } a[pos] =  val;
    return a;
}

/*  a: input array, {1, 7, 6, 4}
    end: array last index, 3 for above case
*/
int getMaxSum (int a [], int end, int sum = 0) {
    if (end == 1) {
        return sum;
    }

    int maxSum = 0;

    for (int i = 1; i < end; i++) {
        auto mult = a[i - 1]*a[i + 1];
        auto val = remove(a, end, i);
        auto tmp = getMaxSum (a, end - 1, sum + mult);
        if (tmp > maxSum)
            maxSum = tmp;
        insert(a, end - 1, i, val);
    }

    return maxSum;
}

Answer 1

This can be solved using modified Matrix Chain Multiplication problem using Dynamic programming.

Suppose given numbers are A, B, C, D

A B C D
1 6 7 4

Now convert these number to:

• matrix M1 of dimensions AxB
• matrix M2 of dimensions BxC

• matrix M3 of dimensions CxD

  M1 M2 M3
  AB BC CD
  16 67 74
  

Normally, if 2 compatible matrices of dimension AB and BC are multiplied then cost of multiplication is AB x BC = ABC. ABC is product of 3 elements A, B & C.

In this modified algorithm, the cost will be AxC (since picking element [i] will result in cost [i-1]x[i+1]).

That is, AB x BC = AC. AC is product of 2 elements A & C.

Now, try to parenthesize the matrices M1, M2 and M3 in all the possible ways such that the cost is maximum.

Possible parentheses:

[1] (M1 (M2 M3))
[2] ((M1 M2) M3) 


[1] 
{AB x (BCxCD)} => {AB x BD}
{(AB) x (6 x 4 = 24)} => {1 x 4 = 4}  ,  so 24 + 4 = 28
Elements picking order {C} -> {B}

[2]
{(AB x BC) x CD} => {AC x CD}
{(1 x 7 = 7) x CD} => {1 x 4 = 4} , so 7 + 4 = 11
Elements picking order {B} -> {C}

So, using [1], the cost is max, i.e. 28, and elements should be picked in following order: C -> B.

Answer 2

Here is a dynamic programming c++ solution which I think is quite close to the Matrix Chain Multiplication idea given by sameerkn. We store in table sums[i][j] the maxSum starting from index i and ending in index j. We iterate over the number of coins between indices starting with sequences of three coins (j-i = 2). The iterative step is to pick for sums[i][j] the largest one of sum[i][k] + sum[k][j] + coins[i]*coins[j]. If j-i<2, m[i][j]=0.

int maxSum(const std::vector<int>& coins){
  int n = coins.size();
  std::vector<std::vector<int>> sums;
  for (int i = 0; i < n-1; ++i){
    sums.push_back(std::vector<int>(n));
  }
  for (int l = 2; l < n; ++l){
    for (int i = 0; i < n - l; ++i){
      int j = i + l;
      sums[i][j] = -1;
      for (int k = i+1; k < j; k++){
        int val = sums[i][k] + sums[k][j] + coins[i]*coins[j];
        if (val > sums[i][j]){
          sums[i][j] = val;
        }
      }
    }
  }
  return sums[0][n-1];
}

As can be seen easily the time complexity is O(N^3) and space is O(N^2).

Answer 3

I would suggest the use of a cache for your function getMaxSum. Actually, it doesn't avoid the exponential complexity of the algorithm, but it saves much time ingoring repeatable calculations. Here's my implementation in Python (because it looks quite sort):

cache = {}

def getMaxSum(a):
    if tuple(a) in cache:
        return cache[tuple(a)]

    sum_arr = []
    for i in range(1, len(a) - 1):
        s = a[i-1] * a[i+1] + getMaxSum(a[:i] + a[i+1:])
        sum_arr.append(s)

    cache[tuple(a)] = max(sum_arr) if sum_arr else 0

    return cache[tuple(a)]

print(getMaxSum([1, 6, 7, 4])) # 28
print(getMaxSum([1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20])) # 3420

It works quite fast for lists with the length up to 20.

As for a non-exponential solution, I think, it's a difficult mathematical question required a serious research to answer.

Answer 4

I managed to solve it with (I think) DP. However, its space requirements is a factor of 2^n where n is the number of coins to be removed.

The basic idea is that we're traversing between points in n-dimensional space.

Say: coins = [ _, x, x, x, _ ]

There are 3 "middle" coins. If we denote the presence (and absence) of the coins by 1s (and 0s), we are traversing from (1, 1, 1) to (0, 0, 0).

In between, there are many transitional states which we might reach through multiple paths.

For eg: (1, 0, 0) might be reached as (1, 1, 1) -> (1, 1, 0) -> (1, 0, 0) or (1, 1, 1) -> (1, 0, 1) -> (1, 0, 0).

So, if the multiplication of adjacent numbers is the score, we can set the value of state (1, 0, 0) to be the higher of the paths leading up to it. As each transition requires "stepping down" by turning one 1 to 0, we can save the value of the states as we iterate from (1, 1, 1) to (0, 0, 0). The final answer will be stored at (0, 0, 0).

Below is one such implementation. I wasn't sure how to go about representing the n-dimensional states. So, I just used an integer that decrements down from 2^n - 1 and then used its binary value to encode the state. So, if cur_state = 6 (110), then it means we have removed the third "middle" coin.

To make the transition, we subtract 2^(index of 1 to be removed) from cur_state.

(Warning: Some ugly index calculations were used to find the adjacent coins of the coin to be removed).

coins = [1, 6, 7, 4]
middle_length = len(coins) - 2
upper_limit = 2**middle_length

values = [0] * upper_limit

for cur_state in range(upper_limit - 1, 0, -1):
    binary = bin(cur_state)[2:].zfill(middle_length)
    for k, a in enumerate(binary):
        if a == '1':
            next_state = cur_state - 2**(middle_length - k - 1)
            left_coin = k - (binary[:k][::-1] + '1').find('1')
            right_coin = (binary[k + 1:] + '1').find('1') + k + 2
            transit_value = (coins[left_coin] * coins[right_coin])
            if values[cur_state] + transit_value > values[next_state]:
                values[next_state] = values[cur_state] + transit_value

print(values[0])

Answer 5

It is easy to show that the problem of best elimination order between indexes i and j can be reduced to the best division of f(i,j) into the two subproblems f(i,k) and f(k,j). Since eventually a[i] must be multiplied by some a[k] when the middle elements have been eliminated (or a[k] is adjacent to a[i]), we can fix i,k,j and apply the function recursively to each subproblem. Base cases are outlined in the JavaScript code below. This solution is essentially the same as Ari Hietanen's.

function f(a,i,j){
  if (Math.abs(i - j) === 2)
    return a[i] * a[j];

  if (Math.abs(i - j) === 1) 
    return 0;

  var best = -Infinity;

  for (var k=i+1; k<j;k++){
    best = Math.max(best, a[i] * a[j] + f(a,i,k) + f(a,k,j));
  }

  return best;
}

var a = [1,6,7,4];

console.log(f(a,0,3)); // 28