4

過去にこれと同様の問題に遭遇しましたが、この問題を解決する方法がまだよくわかりません。問題は次のようになります。

サイズ n <= 1000 および k <= n の正の整数配列が与えられます。これは、配列を分割する必要がある連続したサブ配列の数です。最小 m を出力する必要があります。ここで、m = max{s[1],..., s[k]} であり、s[i] は i 番目の部分配列の合計です。配列内のすべての整数は 1 ～ 100 です。例:

Input:                           Output:
5  3  >> n = 5 k = 3             3
2 1 1 2 3

配列を 2+1 に分割 | 1+2 | 3 は m を最小化します。

私の強引なアイデアは、最初のサブアレイを位置 i で終了させ (可能なすべての i に対して)、可能な限り最良の方法で残りのアレイを k-1 サブアレイに分割しようとすることでした。ただし、これは指数関数的なソリューションであり、決して機能しません。

だから私はそれを解決するための良いアイデアを探しています。もしお持ちでしたら教えてください。

ご協力いただきありがとうございます。

4

6 に答える 6

5

この問題は動的計画法を使用して解決できますが、実際には、答えに対して貪欲な二分探索を使用して解決できます。このアルゴリズムの複雑さは ですO(n log d)。dは出力の答えです。(上限は、配列内のすべての要素の合計になります。) (またはO( n d )出力ビットのサイズ)

アイデアは、あなたがどうなるかをバイナリ検索するmことです-そして、現在の要素を追加して現在の要素を現在の要素にプッシュしない限り、現在の要素をパーティションに追加しmます-その場合、新しいパーティションを開始します。m使用されているパーティションの数が指定された入力以下の場合、現在は成功です (したがって、上限を調整します) k。そうしないと、使用するパーティションが多すぎて、 の下限を上げてしまいますm。

擬似コード:

// binary search
binary_search ( array, N, k ) {
    lower = max( array ), upper = sum( array )

    while lower < upper {
        mid = ( lower + upper ) / 2

        // if the greedy is good
        if partitions( array, mid ) <= k
           upper = mid
        else
           lower = mid
    }
 }

 partitions( array, m ) {
    count = 0
    running_sum = 0

    for x in array {
       if running_sum + x > m
          running_sum = 0
          count++
       running_sum += x
    }
    if running_sum > 0
       count++
    return count
 }

これは、概念的に考え出すのが簡単なはずです。dまた、パーティション関数の単調な性質のため、出力が大きすぎないことが確実な場合は、実際には二分探索をスキップして線形探索を実行できます。

 for i = 0 to infinity
    if partitions( array, i ) <= k
       return i
于 2011-12-21T18:42:52.103 に答える
3

動的プログラミング。配列を作る

int best[k+1][n+1];

配列intサブ配列best[i][j]の最初の要素を分割することで達成できる最高の場所はどこですか。単純に最初の配列要素の合計です。rowがあれば、次のように row を計算します。jibest[1][j]jii+1

for(j = i+1; j <= n; ++j){
    temp = min(best[i][i], arraysum[i+1 .. j]);
    for(h = i+1; h < j; ++h){
        if (min(best[i][h], arraysum[h+1 .. j]) < temp){
            temp = min(best[i][h], arraysum[h+1 .. j]);
        }
    }
    best[i+1][j] = temp;
}

best[m][n]ソリューションが含まれます。アルゴリズムは O(n^2*k) ですが、おそらくもっと良いものが可能です。

編集: ChingPing、toto2、Coffee on Mars、および rds のアイデアの組み合わせ (現在このページに表示されている順序で)。

設定しA = ceiling(sum/k)ます。これは最小値の下限です。最小値の適切な上限を見つけるには、上記のいずれかの方法で適切なパーティションを作成し、最大部分和を減少させる単純な移動が見つからなくなるまで境界線を移動します。これにより、上限 B が得られますが、下限よりもはるかに大きくはありません (それがはるかに大きい場合は、境界線を移動することで簡単に改善できると思います)。ここで、可能な分岐の数を減らす既知の上限を使用して、ChingPing のアルゴリズムに進みます。この最後のフェーズは O((BA)*n) であり、B不明ですが、O(n^2) よりも優れていると思います。

于 2011-12-21T15:58:50.053 に答える
2

私は厄介な分岐とバインドのアルゴリズムを持っています (私に反対票を投じないでください)

最初に配列の合計を取り、k で除算します。これにより、答えに対する最良のケースの範囲、つまり平均 A が得られます。また、これまでに見られたすべての分岐 GO (グローバル最適) の最良の解を保持します。いくつかの配列要素の後のパーティション単位としてのdivider( logical )で、k-1個のパーティションを配置する必要があります。このようにパーティションを貪欲に配置します。

次の位置でAを超えることがわかるまで、それらを合計する配列要素をトラバースし、この位置に仕切りを置く場所と次の位置に置く場所の2つの分岐を作成します。これを再帰的に行い、GO = minを設定します（GO、ブランチの答え）。任意のブランチの任意の時点で、GO より大きいパーティションがある場合、または位置番号が小さい場合、配置するために残っているパーティションがバインドされます。最後に、答えたときに GO が必要です。

編集: ダニエルが示唆したように、A として要素の合計に達するか、残りの位置が仕切りよりも少なくなるまで配置するために、仕切りの配置戦略を少し変更できます。

于 2011-12-21T15:59:12.907 に答える
1

これは単なるアイデアのスケッチです...うまくいくかどうかはわかりませんが、非常に簡単です (そしておそらく高速です)。

分版を均等に配置することから始めます (実際にどのように開始するかは問題ではありません)。

各部分配列の合計を作成します。
合計が最大の部分配列を見つけます。
右側と左側の隣接するサブ配列を見て、左側のサブ配列の合計が右側のサブ配列よりも小さい場合 (またはその逆)、左側の分離を 1 つ移動します。
現在の合計が最大の部分配列に対してやり直します。

同じ 2 つの位置の間の分離をバウンスし続ける状況に到達する可能性があります。これは、おそらく解決策があることを意味します。

編集: @rds によるコメントを参照してください。バウンス ソリューションと終了条件については、もっとよく考える必要があります。

于 2011-12-21T16:11:09.940 に答える
0

残念ながらうまくいかない私の考え：

  1. 配列を N 個の部分配列に分割します
  2. 合計が最小である 2 つの連続する部分配列を見つけます
  3. 手順 2 で見つかったサブ配列をマージして、新しい連続したサブ配列を形成します。
  4. サブアレイの総数が k より大きい場合は、ステップ 2 から繰り返します。そうでない場合は終了します。
于 2011-12-21T16:20:19.050 に答える
0

配列に乱数がある場合、各サブ配列に n/k があるパーティションが適切な出発点になることを期待できます。

そこから

  1. 合計を計算して、この解候補を評価します。
  2. この解候補を保存します。たとえば、次のようにします。
    • すべてのサブ配列のインデックスの配列
    • サブ配列の合計の対応する最大値
  3. max サブ配列のサイズを減らします。2 つの新しい候補を作成します。1 つは index+1 で始まるサブ配列を持ちます。インデックス 1 で終わる部分配列を持つもの
  4. 新しい候補者を評価します。
    • それらの最大値が高い場合は破棄します
    • 最大値が低い場合は、この候補が既に評価されている場合を除いて、2 を繰り返します。その場合、それが解決策です。
于 2011-12-21T16:12:50.297 に答える