3

N x N行列が与えられ、N <= 25各セルが正の整数値を持つ場合、どうすればそれを最大で K 行 (直線の上下の線または直線の左右の線) で分割できますか [注: 片側からother]) 最大値グループ (パーティションによって決定される) が最小になるようにしますか?

たとえば、次の行列があるとします。

1 1 2
1 1 2 
2 2 4

そして、それを分割するために 2 本の線を使用することができます。列 2 と 3 の間に線を引き、行 2 と 3 の間に線を引き、最小化された最大値 4 を与えます。

私が最初に考えたのは、各行の状態を表すビットマスクであり、それを表す 2 つの整数があると思います。ただし、これは遅すぎます。複雑さはO(2^(2N))おそらく、行で解決してから、列で解決できますか?

誰にもアイデアはありますか？

編集：グーグルで検索した後の問題は次のとおりです：http://www.sciencedirect.com/science/article/pii/0166218X94001546

別の論文: http://cis.poly.edu/suel/papers/pxp.pdf

読んでみます＾＾

4

1 に答える 1

0

垂直線のすべてのサブセットを試してから、水平線の動的プログラミングを行うことができます。

垂直線のセットを S として固定したとします。垂直線の固定セット S を D(K, S) として行列の最初の K 行からなる部分問題の答えを示します。この場合、より小さいサイズの部分問題で D(K, S) を解くための再帰を見つけるのは自明です。

最初に各部分行列のサイズを事前計算する場合、全体的な複雑さは O(2^N * N^2) になります。

于 2013-02-25T14:34:56.103 に答える