0

問題は次のとおりです。数列が与えられた場合、これらの数を 2 つの数列に分割して、2 つの数列の差が最小になるようにします。たとえば、シーケンスが [5, 4, 3, 3, 3] の場合、解は
[5, 4] -> 合計は 9
[3, 3, 3] -> 合計は 9
差は 0 です。

言い換えると、整数の入力ベクトル (可変サイズ) を指定して、2 つの合計の差が最小になる 2 つのベクトルを出力できるアルゴリズム (C 言語を推奨) を見つけることができますか?
残忍な力のアルゴリズムは避けるべきです。

適切なソリューションを確実に得るために、アルゴリズムと残忍な力のアルゴリズムの結果をベンチマークで比較するとよいでしょう。

4

1 に答える 1

2

サブアレイの問題のように聞こえます（これは「シーケンス」の私の解釈です）。

意味する唯一の可能性5, 4, 3, 3, 3は次のとおりです。

| 5, 4, 3, 3, 3  =>  0 - 18 => 18
 5 | 4, 3, 3, 3  =>  5 - 13 => 8
 5, 4 | 3, 3, 3  =>  9 -  9 => 0
 5, 4, 3 | 3, 3  => 12 -  6 => 6
 5, 4, 3, 3 | 3  => 15 -  3 => 12
 5, 4, 3, 3, 3 | => 18 -  0 => 18 (same as first)

すべてのインデックスの両側の合計を比較するのと同じくらい簡単です。

コード: (未テスト)

int total = 0;
for (int i = 0; i < n; i++)
  total += arr[i];
int best = INT_MAX, bestPos = -1, current = 0;
for (int i = 0; i < n; i++)
{
  current += arr[i];
  int diff = abs(current - total);
  if (diff < best)
  {
    best = diff;
    bestPos = i;
  }
  // else break; - optimisation, may not work
}

printf("The best position is at %d\n", bestPos);

上記はO(n)、論理的には、それ以上のことはできません。

シーケンスに対してバイナリ検索のようなプロセスn + log nを実行して、ではなくに到達することで、上記をわずかに最適化できます2nが、どちらもO(n). 基本的な擬似コード:

sum[0] = arr[0]
// sum[i] represents sum from indices 0 to i
for (i = 1:n)
  sum[i] = sum[i-1] + arr[i]
total = sum[n]
start = 0
end = n
best = MAX
repeat:
  if (start == end) stop
  mid = (start + end) / 2
  sumFromMidToN = sum[n] - sum[mid]
  best = max(best, abs(sumFromMidToN - sum[mid]))
  if (sum[mid] > sumFromMidToN)
    end = mid
  else if (sum[mid] < sumFromMidToN)
    start = mid
  else
    stop

それが実際にサブセットである場合、すでに述べたように、それは分割問題の最適化バージョンのように見えますが、これははるかに困難です。

于 2013-03-18T09:28:07.610 に答える