不同面额的硬币依次放置，挑选硬币使总和最大

Question

不同面额的硬币依次放置。您需要一个接一个地挑选硬币（除了第一个和最后一个），直到只剩下 2 个硬币（第一个和最后一个）。每次您选择一枚硬币时，您将其乘以左硬币和右硬币的值。问题是按照这样的顺序挑选硬币，使得所有乘法的总和最大。例如：

假设硬币被放置为 1、6、7、4

有两种拾取硬币的方法：

第一种方式：先选6，这样会得到1*7 = 7，然后再选7，这样会得到1*4 = 4，所以总数是7 + 4 = 11

第二种方式：先选7，这样会得到6*4 = 24，然后再选6，这样会得到1*4 = 4，所以总数是24 + 4 = 28

因为 28 是最大的，所以这就是我们的答案。

我可以通过递归遍历所有可能的情况并比较它们的输出值来找到正确的答案，但是这个解决方案非常低效，因为它需要指数时间。请告知如何更有效地解决此问题。

编辑： 递归解法

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

这可以通过修改 Matrix Chain Multiplication problem using Dynamic programming 来解决。

假设给定的数字是 A、B、C、D

A B C D
1 6 7 4

现在将这些数字转换为：

维度为 AxB 的矩阵 M1
维度为 BxC 的矩阵 M2
维度为 CxD 的矩阵 M3
```
M1 M2 M3
AB BC CD
16 67 74
```

通常情况下，如果将 2 个 AB 和 BC 维兼容矩阵相乘，则乘法成本为 AB x BC = ABC。 ABC is product of 3 elements A, B & C.

在此修改后的算法中，成本将为 AxC（因为选择元素 [i] 将导致成本 [i-1]x[i+1]）。

即AB x BC = AC。 AC is product of 2 elements A & C.

现在，尝试以所有可能的方式将矩阵 M1、M2 和 M3 括起来，以使成本最大。

可能的括号：

[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}

因此，使用[1]，成本最大，即28，应按以下顺序选择元素：C -> B。

Answer 2

我建议为您的函数使用缓存 getMaxSum。实际上，它并没有避免算法的指数复杂度，但是它节省了很多重复计算的时间。这是我在 Python 中的实现（因为它看起来很不错）：

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

对于长度最大为 20 的列表，它工作得非常快。

至于非指数解，我认为，这是一个需要认真研究才能回答的数学难题。

Answer 3

这是一个动态编程的c++解决方案，我认为它非常接近samerkn给出的矩阵链乘法思想。我们在 table sums[i][j] 中存储从索引 i 开始到索引 j 结束的 maxSum。我们以三个硬币的序列 (j-i = 2) 开始迭代索引之间的硬币数量。迭代步骤是为 sums[i][j] 选择 sum[i][k] + sum[k][j] + coins[i]*coins[j] 中最大的一个。如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];
}

很容易看出时间复杂度是O(N^3)，space是O(N^2)。

Answer 4

我设法用（我认为）DP 解决了它。但是，它的 space 要求是 2^n 的因数，其中 n 是要移除的硬币数量。

基本思想是我们在 n 维的点之间遍历 space。

说：coins = [ _, x, x, x, _ ]

有 3 个 "middle" 硬币。如果我们用 1s（和 0s）表示硬币的存在（和不存在），我们就是从 (1, 1, 1) 遍历到 (0, 0, 0)。

在这两者之间，有许多过渡状态，我们可能会通过多条路径到达。

例如：(1, 0, 0) 可能达到 (1, 1, 1) -> (1, 1, 0) -> (1, 0, 0) 或 (1, 1, 1) -> (1, 0, 1) - > (1, 0, 0)。

因此，如果相邻数字的乘积是分数，我们可以将状态 (1, 0, 0) 的 value 设置为通往它的路径中较高的一个。由于每个转换都需要 "stepping down"，将一个 1 转换为 0，我们可以在从 (1, 1, 1) 迭代到 (0, 0, 0) 时保存状态值。最终答案将存储在 (0, 0, 0)。

下面是一个这样的实现。我不确定如何去表示 n 维状态。所以，我只是使用了一个从 2^n - 1 递减的整数，然后使用它的二进制值来编码状态。所以，如果 cur_state = 6 (110)，则意味着我们已经移除了第三个 "middle" 硬币。

为了进行转换，我们从 cur_state 中减去 2^(index of 1 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

很容易证明索引i和j之间的最佳消元顺序问题可以归结为f(i,j)最好划分为两个子问题f(i,k) 和 f(k,j)。由于最终 a[i] 必须乘以一些 a[k] 当中间元素被消除时（或者 a[k] 与 a[i] 相邻），我们可以固定 i,k,j 和递归地将函数应用于每个子问题。下面的 JavaScript 代码概述了基本情况。此解决方案与 Ari Hietanen 的解决方案基本相同。

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

不同面额的硬币依次放置，挑选硬币使总和最大

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

puzzle

algorithm