不同面额的硬币一个接一个地放置,挑选硬币以最大化总和

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

这可以通过使用动态编程修改矩阵链乘法问题来解决。

假设给定数字是 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。