以下は、指数関数的な複雑さよりも小さい複雑さでは答えられないインタビューの質問です。DPの問題のようですが、ベースケースを作成して適切に分析することができません。どんな助けでも大歓迎です。
それぞれサイズ'n'の2つの配列が与えられます。新しい配列で連続する要素の積の合計が最大になるように、これらの配列を安定してマージする必要があります。
例えば
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が最大になります。
同じ問題の解決策としてc[i、j]を定義しましょう。ただし、配列はiから始まり左に終わります。そして、jは右に終わります。したがって、c[0,0]は元の問題の解決策を提供します。
c [i、j]はで構成されます。
次に、この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を使用してパスをトレースバックします。
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] = max {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] = max {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から取得する必要があります）。
安定したマージとF(i, j)によって達成できる最大のペアワイズ和として定義します。Ai...AnBj...Bn
マージの各ステップで、次の3つのオプションのいずれかを選択できます。
Aます。Aとの最初の残りの要素を取りBます。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
)
2つのリストの最適なマージを見つけるには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が選択されたかをキャッシュしてバックトラックする必要もあります。
私の解決策はかなり単純です。考えられるすべての安定したマージについて調べます。動作中の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;
}
動的計画法によってそれを解決する1つの方法は、常に以下を保存することです。
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]);
それをマージして並べ替えます。マージソートの可能性があります。ソートされた配列は最大値を示します（マージは配列を追加するだけです）。複雑さはnlognです。
殴られた道から少し離れたところに興味がある場合は、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)
テストケースをもう少し提供したほうがいいと思います。しかし、マージソートで行われるマージと同様の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 2Compare 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}
私はそれについて多くの研究をしていません。したがって、失敗する可能性のあるテストケースがある場合は、それを提供してください。