1

私は次の動的計画法の問題に遭遇しました。

整数のグリッドがあります（負の数を含む）。数値の合計が最大の長方形を見つけます。

マトリックス全体に対してそれを行う方法はありますか？

私はそれを単一の配列について解いたので、最長増加部分列問題が行うことをほぼ追跡しましたが、連続した数についてのみでした。 

def array_largest_block(sequence)
  len = sequence.size
  parents = [nil]*len
  my_largest = sequence
  largest = sequence.max

  for index in (1...len)
    if my_largest[index] < my_largest[index] + my_largest[index - 1]
      my_largest[index] = my_largest[index] + my_largest[index - 1]
      parents[index] = index - 1
      largest = [largest, my_largest[index]].max
    end
  end

  end_index_of_largest_block = my_largest.find_index(largest)
  i = end_index_of_largest_block
  res = []
  res << sequence[i]
  while !parents[i].nil?
    i = parents[i]
    res << sequence[i]
  end
  return {l_sum: largest, start: i, end: end_index_of_largest_block}
end

だから私の考えは、

  1. マトリックス内の各正方形の合計を求めます（1x1の正方形のみ）
  2. 可能な答えのために最大値を保存します
  3. 可能な限り最小の長方形から始めて同じことを実行し、最大値が見つかるまでそれらすべてを計算します。これはDB部分です。

何か案は？または、正確な解決策がわからない場合は、どのDPタイプのアルゴリズムを検討する必要がありますか？

4

2 に答える 2

5

これはで行うことができますO(N^3)。ここNで、は行列のサイズです。

基本的に、長方形の左右の列を選択し、線形時間で行をスキャンします（事前に計算された合計を使用）。

int totalBestSum = -10000000;
for (int leftCol = 1; leftCol <= N; leftCol++)
   for (int rightCol = leftCol; rightCol <= N; rightCol++)
   {
      int curSum = 0, curBestSum = -10000000;
      for (int row = 1; row <= N; row++) {
         int rowSum = sumBetween(leftCol, rightCol, row);
         curSum += rowSum;
         if (curSum > curBestSum) curBestSum = curSum;
         if (curSum < 0) curSum = 0;                   
      }

      if (curBestSum > totalBestSum) totalBestSum = curBestSum;
   }

sumBetween2つの列の間の特定の行の数値の合計を返す関数です。事前に計算された合計を使用して、一定時間で実装できます。

int sumBetween(int leftCol, int rightCol, int row)
{
    return sum[row][rightCol] - sum[row][leftCol - 1];
}

sum配列を計算するには：

for (int row = 1; row <= N; row++)
   for (int col = 1; col <= N; col++)
      sum[row][col] = sum[row][col - 1] + matrix[row][col];
于 2012-10-08T17:11:49.407 に答える
1

重複しているように見えますが、それでも、ここを見てください：最大の合計で部分行列を取得しますか？

で行うことが可能ですO(N^3)。

そして、一体なぜ「NP完全」タグを使用するのですか？：D

于 2012-10-08T17:11:52.430 に答える