Trợ giúp thuật toán: cách phân chia mảng thành N đoạn với phân đoạn lớn nhất có thể (phân đoạn cân bằng)

Question

Tôi đã gặp vấn đề này trên một trong các diễn đàn lập trình tiếng Nga, nhưng chưa đưa ra giải pháp thanh lịch.

Vấn đề:

Bạn có một mảng với N số nguyên dương, bạn cần phải chia nó thành M phân đoạn tiếp giáp, do đó tổng của phân khúc lớn nhất là giá trị nhỏ nhất có thể. Theo tổng số của phân đoạn, tôi có nghĩa là tổng của tất cả các số nguyên của nó. Nói cách khác, tôi muốn phân đoạn mảng cân bằng tốt, nơi bạn không muốn một phân đoạn đơn lẻ quá lớn.

Ví dụ:

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

• M = 3, có nghĩa là tôi cần phải chia mảng của tôi vào 3 subarrays .

• Giải pháp sẽ là: [4,7] [12, 5] [3, 16] sao cho phân khúc lớn nhất là [3, 16] = 19 và không có biến thể phân khúc nào khác có thể tạo phân đoạn lớn nhất với tổng số nhỏ hơn .

Một ví dụ khác:

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

Giải pháp: [3, 13, 5] [7, 18] [8] [20, 1], phân đoạn "béo nhất" là [7, 18] = 25 (đúng với tôi nếu tôi sai, tôi đã tạo ra ví dụ này)

Tôi có cảm giác rằng đây là một số vấn đề CS/toán kinh điển, có lẽ với một số tên người nổi tiếng liên kết với nó, giống như vấn đề của Dijkstra. - Có giải pháp nào cho nó không? - Nếu không, bạn có thể đưa ra một số giải pháp khác ngoài việc ép buộc không, đó là, theo như tôi hiểu phức tạp về thời gian, theo cấp số mũ. (N^M, cụ thể hơn).

Cảm ơn trước, stackoverflowers.

Answer 1

Tôi thích ILoveCoding's approach. Đây là một cách khác mất O (MN^2) thời gian, sẽ nhanh hơn nếu N và M nhỏ nhưng số trong mảng rất lớn (cụ thể, nếu log (tổng) >> MN, có thể nhưng thừa nhận không có vẻ rất thực tế). Nó sử dụng lập trình động.

Hãy xem xét phân vùng chỉ phần phụ bao gồm các đầu tiên i < = N mục nhập vào j < = M phân đoạn. Gọi f (i, j) là trọng số của phân đoạn lớn nhất trong giải pháp tốt nhất cho bài toán con này - nghĩa là trọng số của phân đoạn lớn nhất trong phân đoạn j của các số i đầu tiên có phân đoạn lớn nhất nhỏ nhất trong tất cả các phân vùng đó. Chúng tôi muốn tính toán f (N, M), cũng như một (có thể có nhiều hơn một) phân vùng tương ứng với nó.

Thật dễ dàng để tính f (i, 1) - đó chỉ là tổng của các yếu tố tôi lần đầu tiên:

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

Để tính f (i, j) với j> = 2, quan sát yếu tố đó tôi phải là phần tử cuối cùng của một đoạn nào đó bắt đầu tại một số vị trí 1 < = k < = i, và trước đó là đoạn j-1 - và trong bất kỳ giải pháp tối ưu nào cho tham số (i, j), 1 phân đoạn trước phải tự tối ưu cho các tham số (k-1, j-1). Vì vậy, nếu chúng tôi xem xét mọi vị trí bắt đầu có thể có k cho phân khúc cuối cùng này và tận dụng tốt nhất, chúng tôi sẽ tính phân đoạn j tốt nhất của các phần tử i đầu tiên:

[EDIT 3/2/2015: Chúng tôi cần thực hiện tối đa của phân khúc mới và phân khúc còn lại lớn nhất, thay vì thêm họ!]

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

Nếu chúng ta thử các giá trị k để giảm, sau đó chúng ta có thể dễ dàng xây dựng tổng trong thời gian liên tục cho mỗi giá trị k, vì vậy tính toán một giá trị f (i, j) duy nhất có thời gian O (N). Chúng ta có MN của các giá trị này để tính toán, vì vậy tổng thời gian cần thiết là O (MN^2).

Một điều kiện biên hơn là cần thiết để cấm cố gắng để phân vùng vào phân đoạn hơn có những yếu tố:

f(i, j > i) = infinity 

Một khi chúng ta đã tính toán f (N, M), chúng ta có thể trích xuất một phân vùng tương ứng bằng cách truy tìm trở lại thông qua ma trận DP theo cách thông thường - nhưng trong trường hợp này, có lẽ dễ dàng hơn khi xây dựng phân vùng bằng thuật toán tham lam của ILoveCoding. Dù bằng cách nào cũng có thời gian O (N).

Answer 2

1. Hãy thực hiện tìm kiếm nhị phân trên câu trả lời.

2. Để có câu trả lời cố định X bạn có thể dễ dàng kiểm tra xem nó có khả thi hay không (chúng tôi chỉ có thể sử dụng thuật toán tham lam (luôn lấy phân khúc dài nhất có thể để tổng của nó là <= X) và so sánh số lượng phân đoạn M).

Tổng thời gian phức tạp là O(N * log(sum of all elements)).

Dưới đây là một số mã giả

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; 
}