Pomoc algorytmu: jak podzielić macierz na N segmentów o najmniejszym możliwym największym segmencie (zbalansowane segmentowanie)

Question

Natknąłem się na ten problem na jednym z rosyjskich forów programowania, ale nie wymyśliłem eleganckiego rozwiązania.

Problem:

Masz tablicę z N liczb całkowitych dodatnich, trzeba podzielić go na M sąsiednich segmentów, tak że całkowita największego segmentu jest najmniejsza możliwa wartość. Według sumy segmentów mam na myśli sumę wszystkich jej liczb całkowitych. Innymi słowy, chcę dobrze zbalansowanej segmentacji macierzy, w której nie chcesz, aby pojedynczy segment był zbyt duży.

przykład:

• tablicy: [4, 7, 12, 5, 3, 16]

• K = 3, co oznacza, że ​​trzeba podzielić mi tablicy do 3 subarrays .

• Rozwiązanie będzie następujące: [4,7] [12, 5] [3, 16], więc największy segment to [3, 16] = 19 i żaden inny wariant segmentacji nie może wytworzyć największego segmentu o mniejszej sumie .

Innym przykładem

• Tablica [3, 13, 5, 7, 18, 8, 20, 1]
• M = 4

Rozwiązanie: [3, 13, 5] [7, 18] [8] [20, 1], "najgrubszy" segment to [7, 18] = 25 (popraw mnie, jeśli się mylę, wymyśliłem ten przykład)

Mam wrażenie, że jest to jakiś klasyczny problem związany z CS/matematyką, prawdopodobnie z powiązanym z nim nazwiskiem słynnej osoby, jak problem Dijkstry. - Czy jest jakieś znane rozwiązanie? - Jeśli nie, to możesz wymyślić jakieś inne rozwiązanie oprócz brutalnego forsowania, które, o ile rozumiem złożoność czasu, jest wykładnikiem wykładniczym . (N^M, żeby być bardziej szczegółowym).

Dzięki z góry, stackoverflowers.

Answer 1

lubię ILoveCoding's approach. Oto inny sposób, który zajmuje O (MN^2) czas, który będzie szybszy, jeśli N i M są małe, ale liczby w tablicy są bardzo duże (konkretnie, jeśli log (suma) >> MN, co jest możliwe, ale co prawda nie brzmi zbyt realistycznie). Wykorzystuje dynamiczne programowanie.

Rozważmy podzielenie na partycje tylko podtablicy składającej się z pierwszych i < = N wpisów w j < = M segmentów. Niech f (i, j) będzie wagą największego segmentu najlepszego rozwiązania dla tego podproblemu - to jest wagi największego segmentu w tej j-partycji pierwszych numerów, których największy segment jest najmniejszy spośród wszystkich takich partycji. Chcemy obliczyć f (N, M), a także (może być ich więcej) odpowiadającą temu partycji.

Łatwo obliczyć f (i, 1) - to po prostu suma pierwszych elementów I:

f(i, 1) = x[1] + ... + x[i] 

Aby obliczyć f (i, j) dla j> = 2, obserwować ten element Muszę być ostatnim elementem jakiegoś segmentu, który zaczyna się w pewnym położeniu 1 < = k < = i, i który jest poprzedzony segmentami j-1 - oraz w dowolnym optymalnym rozwiązaniu dla parametrów (i, j), te j- 1 poprzednie segmenty muszą same być optymalne dla parametrów (k-1, j-1). Jeśli więc weźmiemy pod uwagę każdą możliwą pozycję początkową k dla tego końcowego segmentu i zrobimy to, co najlepsze, obliczymy najlepsze partycje j pierwszych pierwszych elementów:

[EDIT 3/2/2015: Musimy przyjąć max nowego segmentu i największym pozostałego odcinka, zamiast dodawania ich!]

f(i, j >= 2) = minimum of (max(f(k-1, j-1), x[k] + ... + x[i])) over all 1 <= k <= i 

Jeśli spróbujemy wartości k malejące, to możemy łatwo budować sumę w stałym czasie jednej wartości k, tak obliczanie pojedynczej wartości f (i, j) zajmuje czas O (N). Mamy MN tych wartości do obliczenia, więc całkowity czas potrzebny to O (MN^2). potrzebne

jeden warunek brzegowy zabronić próby podzielić na większą liczbę odcinków niż są elementy:

f(i, j > i) = infinity 

Po obliczyliśmy F (n, m), można było wyodrębnić partycji, przez identyfikację poprzez matrycę DP w zwykły sposób - ale w tym przypadku prawdopodobnie łatwiej jest zbudować partycję za pomocą chciwego algorytmu ILoveCoding. W obu przypadkach czas O (N).

Answer 2

1. Zróbmy wyszukiwanie binarne nad odpowiedzią.

2. za ustaloną odpowiedź X łatwo jest sprawdzić, czy jest to wykonalne, czy nie (możemy po prostu użyć chciwy algorytm (zawsze biorąc najdłuższy odcinek tak, że jego suma jest <= X) i porównać liczbę segmentów M).

Całkowity czas złożoności to O(N * log(sum of all elements)).

Oto pseudokod

boolean isFeasible(int[] array, long candidate, int m) { 
    // Here goes the greedy algorithm. 
    // It finds the minimum number of segments we can get(minSegments). 
    ... 
    return minSegments <= m; 
} 

long getMinimumSum(int[] array, int m) { 
    long low = 0; // too small 
    long high = sum of elements of the array // definitely big enough 
    while (high - low > 1) { 
     long mid = low + (high - low)/2; 
     if (isFeasible(array, mid, m)) 
      high = mid; 
     else 
      low = mid; 
    } 
    return high; 
}