7

以下是一个面试问题，我无法以低于指数复杂性的复杂性回答。虽然这似乎是一个 DP 问题，但我无法形成基本案例并正确分析它。任何帮助表示赞赏。

您将获得 2 个大小为“n”的数组。您需要稳定合并这些数组，以便在新数组中连续元素的乘积之和最大化。

例如

A= { 2, 1, 5}

B= { 3, 7, 9}

稳定合并 A = {a1, a2, a3} 和 B = {b1, b2, b3} 将创建一个包含 2*n 个元素的数组 C。例如，通过合并（稳定）A 和 B 说 C = { b1, a1, a2, a3, b2, b3 }。那么总和 = b1*a1 + a2*a3 + b2*b3 应该是最大值。

4

8 回答 8

3

让我们将 c[i,j] 定义为相同问题的解决方案，但数组从 i 开始到左侧结束。和 j 以右结束。所以 c[0,0] 将为原始问题提供解决方案。

c[i,j] 由。

  1. MaxValue = 最大值。
  2. NeedsPairing = true 或 false = 取决于最左边的元素是否未配对。
  3. Child = [p,q] 或 NULL = 定义子键，最终达到此级别的最佳总和。

现在为这个 DP 定义最优子结构

c[i,j] = if(NeedsPairing) { left[i]*right[j] } + Max { c[i+1, j], c[i, j+1] }

此代码中更详细地捕获了它。

if (lstart == lend)
{
    if (rstart == rend)
    {
        nodeResult = new NodeData() { Max = 0, Child = null, NeedsPairing = false };
    }
    else
    {
        nodeResult = new NodeData()
        {
            Max = ComputeMax(right, rstart),
            NeedsPairing = (rend - rstart) % 2 != 0,
            Child = null
        };
    }
}
else
{
    if (rstart == rend)
    {
        nodeResult = new NodeData()
        {
            Max = ComputeMax(left, lstart),
            NeedsPairing = (lend - lstart) % 2 != 0,
            Child = null
        };
    }
    else
    {
        var downLef = Solve(left, lstart + 1, right, rstart);

        var lefResNode = new NodeData()
        {
            Child = Tuple.Create(lstart + 1, rstart),
        };

        if (downLef.NeedsPairing)
        {
            lefResNode.Max = downLef.Max + left[lstart] * right[rstart];
            lefResNode.NeedsPairing = false;
        }
        else
        {
            lefResNode.Max = downLef.Max;
            lefResNode.NeedsPairing = true;
        }

        var downRt = Solve(left, lstart, right, rstart + 1);

        var rtResNode = new NodeData()
        {
            Child = Tuple.Create(lstart, rstart + 1),
        };

        if (downRt.NeedsPairing)
        {
            rtResNode.Max = downRt.Max + right[rstart] * left[lstart];
            rtResNode.NeedsPairing = false;
        }
        else
        {
            rtResNode.Max = downRt.Max;
            rtResNode.NeedsPairing = true;
        }

        if (lefResNode.Max > rtResNode.Max)
        {
            nodeResult = lefResNode;
        }
        else
        {
            nodeResult = rtResNode;
        }
    }
}

我们使用记忆来防止再次解决子问题。

Dictionary<Tuple<int, int>, NodeData> memoization = new Dictionary<Tuple<int, int>, NodeData>();

最后我们使用 NodeData.Child 来追溯路径。

于 2012-08-05T01:37:08.153 回答
1

对于 A = {a1,a2,...,an}，B = {b1,b2,...,bn}，

将 DP[i,j] 定义为 {ai,...,an} 和 {bj,...,bn} 之间的最大稳定合并和。

(1 <= i <= n+1, 1 <= j <= n+1)

DP[n+1,n+1] = 0, DP[n+1,k] = bk*bk+1 +...+ bn-1*bn, DP[k,n+1] = ak*ak +1 +...+ an-1*an。

DP[n,k] = 最大{an*bk + bk+1*bk+2 +..+ bn-1*bn, DP[n,k+2] + bk*bk+1}

DP[k,n] = max{ak*bn + ak+1*ak+2 +..+ an-1*an, DP[k+2,n] + ak*ak+1}

DP[i,j] = 最大{DP[i+2,j] + ai*ai+1, DP[i,j+2] + bi*bi+1, DP[i+1,j+1] + ai*bi}。

然后你返回 DP[1,1]。

说明：在每个步骤中，您必须考虑 3 个选项：从剩余的 A 中获取前 2 个元素，从剩余的 B 中获取前 2 个元素，或者从 A 和 B 中同时获取（由于您无法更改 A 和 B 的顺序，您将不得不从 A 中获取第一个，从 B 中获取第一个）。

于 2012-07-27T07:38:04.083 回答
0

这是 Clojure 中的一个解决方案，如果您对更偏僻的东西感兴趣的话。它是 O(n 3 )，因为它只生成所有 n 2 个稳定合并并花费 n 时间对乘积求和。与我见过的基于数组的命令式解决方案相比，偏移量和算术的混乱要少得多，这有望使算法更加突出。而且它也非常灵活：例如，如果您想包含 c2*c3 以及 c1*c2 和 c3*c4，您可以简单地替换(partition 2 coll)为(partition 2 1 coll).

;; return a list of all possible ways to stably merge the two input collections
(defn stable-merges [xs ys]
  (lazy-seq
   (cond (empty? xs) [ys]
         (empty? ys) [xs]
         :else (concat (let [[x & xs] xs]
                         (for [merge (stable-merges xs ys)]
                           (cons x merge)))
                       (let [[y & ys] ys]
                         (for [merge (stable-merges xs ys)]
                           (cons y merge)))))))

;; split up into chunks of two, multiply, and add the results
(defn sum-of-products [coll]
  (apply + (for [[a b] (partition 2 coll)]
             (* a b))))

;; try all the merges, find the one with the biggest sum
(defn best-merge [xs ys]
  (apply max-key sum-of-products (stable-merges xs ys)))

user> (best-merge [2 1 5] [3 7 9])
(2 1 3 5 7 9)
于 2012-08-05T01:28:37.893 回答
0

定义为通过稳定合并和F(i, j)可以实现的最大成对和。Ai...AnBj...Bn

在合并的每一步，我们可以选择以下三个选项之一：

  1. 取 的前两个剩余元素A。
  2. 取 的第一个剩余元素A和 的第一个剩余元素B。
  3. 取 的前两个剩余元素B。

因此，F(i, j)可以递归定义为：

F(n, n) = 0
F(i, j) = max
(
    AiAi+1 + F(i+2, j), //Option 1
    AiBj + F(i+1, j+1), //Option 2
    BjBj+1 + F(i, j+2)  //Option 3
)

为了找到两个列表的最佳合并，我们需要F(0, 0)天真地找到 ，这将涉及多次计算中间值，但是通过缓存每个F(i, j)找到的值，复杂性降低到O(n^2)。

这是一些快速而肮脏的c ++，它可以做到这一点：

#include <iostream>

#define INVALID -1

int max(int p, int q, int r)
{
    return p >= q && p >= r ? p : q >= r ? q : r;
}

int F(int i, int j, int * a, int * b, int len, int * cache)
{
    if (cache[i * (len + 1) + j] != INVALID)    
        return cache[i * (len + 1) + j];

    int p = 0, q = 0, r = 0;

    if (i < len && j < len)
        p = a[i] * b[j] + F(i + 1, j + 1, a, b, len, cache);

    if (i + 1 < len)
        q = a[i] * a[i + 1] + F(i + 2, j, a, b, len, cache);

    if (j + 1 < len)
        r = b[j] * b[j + 1] + F(i, j + 2, a, b, len, cache);

    return cache[i * (len + 1) + j] = max(p, q, r);
}

int main(int argc, char ** argv)
{
    int a[] = {2, 1, 3};
    int b[] = {3, 7, 9};
    int len = 3;

    int cache[(len + 1) * (len + 1)];
    for (int i = 0; i < (len + 1) * (len + 1); i++)
        cache[i] = INVALID;

    cache[(len + 1) * (len + 1)  - 1] = 0;

    std::cout << F(0, 0, a, b, len, cache) << std::endl;
}

如果您需要实际的合并序列而不仅仅是总和，您还必须缓存哪个p, q, r被选中并回溯。

于 2012-07-29T14:35:07.710 回答
0

通过动态编程解决它的一种方法是始终存储：

S[ i ][ j ][ l ] = "合并 A[1,...,i] 和 B[1,...,j] 的最佳方法，如果 l == 0，则最后一个元素是A[i]，如果 l == 1，则最后一个元素是 B[j]"。

然后，DP 将是（伪代码，在 A[0] 和 B[0] 处插入任意数字，并让实际输入在 A[1]...A[n], B[1].. .B[n]):

S[0][0][0] = S[0][0][1] = S[1][0][0] = S[0][1][1] = 0; // If there is only 0 or 1 element at the merged vector, the answer is 0
S[1][0][1] = S[0][1][1] = -infinity; // These two cases are impossible
for i = 1...n:
    for j = 1...n:
        // Note that the cases involving A[0] or B[0] are correctly handled by "-infinity"
        // First consider the case when the last element is A[i]
        S[i][j][0] = max(S[i-1][j][0] + A[i-1]*A[i], // The second to last is A[i-1].
                         S[i-1][j][1] + B[j]*A[i]); // The second to last is B[j]
        // Similarly consider when the last element is B[j]
        S[i][j][1] = max(S[i][j-1][0] + A[i]*B[j], // The second to last is A[i]
                         S[i][j-1][1] + B[j-1]*B[j]); // The second to last is B[j-1]
 // The answer is the best way to merge all elements of A and B, leaving either A[n] or B[n] at the end.
return max(S[n][n][0], S[n][n][1]);
于 2012-07-30T20:49:48.317 回答
0

合并并排序。可能是归并排序。排序后的数组给出最大值。（合并只是附加数组）。复杂度为 nlogn。

于 2012-08-01T11:09:17.067 回答
0

我的解决方案相当简单。我只是探索所有可能的稳定合并。在工作的 C++ 程序之后：

#include<iostream>

using namespace std;

void find_max_sum(int *arr1, int len1, int *arr2, int len2, int sum, int& max_sum){
  if(len1 >= 2)
    find_max_sum(arr1+2, len1-2, arr2, len2, sum+(arr1[0]*arr1[1]), max_sum);
  if(len1 >= 1 && len2 >= 1)
    find_max_sum(arr1+1, len1-1, arr2+1, len2-1, sum+(arr1[0]*arr2[0]), max_sum);
  if(len2 >= 2)
    find_max_sum(arr1, len1, arr2+2, len2-2, sum+(arr2[0]*arr2[1]), max_sum);
  if(len1 == 0 && len2 == 0 && sum > max_sum)
    max_sum = sum;
}

int main(){
  int arr1[3] = {2,1,3};
  int arr2[3] = {3,7,9};
  int max_sum=0;
  find_max_sum(arr1, 3, arr2, 3, 0, max_sum);
  cout<<max_sum<<endl;
  return 0;
}
于 2012-07-29T12:41:44.120 回答
-2

我认为如果您提供更多的测试用例会更好。但我认为两个数组的正常合并类似于在合并排序中完成的合并将解决问题。

合并数组的伪代码在Wiki上给出。

基本上是正常的merging algorithm used in Merge Sort。在合并排序中，数组是排序的，但在这里我们对未排序的数组应用相同的合并算法。

Step 0: 设i为 的索引，first array(A)为j) index for second array(B。i=0 , j=0

Step 1: Compare A[i]=2 & B[j]=3. 因为2<3它将是新的第一个元素merged array(C)。i=1, j=0（将该数字添加到较小的新数组中）

Step 2: 再次Compare A[i]=1 and B[j]=3. 1<3因此insert 1 in C. i++, j=0;

Step 3: 再次Compare A[i]=3 and B[j]=3。Any number can go in C(both are same). i++, j=0;（基本上我们正在增加插入数字的那个数组的索引）

Step 4: 既然array A is complete直接直接insert the elements of Array B in C。否则重复前面的步骤。

Array C = { 2, 1, 3, 3, 7,9}

我对此没有做太多研究。因此，如果有任何可能失败的测试用例，请提供一个。

于 2012-07-29T13:36:45.693 回答