Tối ưu phân thức (Dinkelbach)

Tối ưu phân thức (fractional programming) là lớp bài toán cực trị một tỉ số dạng ${\displaystyle \frac{\sum p_i{x}_i}{\sum q_i{x}_i}}$ trên một tập ràng buộc. Ví dụ điển hình: chọn tập con để trung bình cộng lớn nhất, tìm chu trình có tỉ lệ chi phí/thời gian nhỏ nhất, hay đồ thị con có mật độ cao nhất. Kỹ thuật Dinkelbach biến bài toán tỉ số (khó tối ưu trực tiếp) thành một chuỗi bài toán tuyến tính hoá dễ hơn nhiều, và hội tụ chỉ sau vài vòng lặp thay vì phải chặt nhị phân hàng chục lần.

Bài toán và vì sao tỉ số khó

Ta muốn cực đại (hoặc cực tiểu) tỉ số

$$R(S)=\frac{f(S)}{g(S)}=\frac{{\sum }_{i\in S}{a}_i}{|S|}$$

trên tập các lời giải hợp lệ $S$. Ở đây tử và mẫu đều phụ thuộc lời giải, nên không thể tách rời để tối ưu từng phần: thêm một phần tử độ khó cao làm tử tăng nhưng mẫu cũng tăng, chưa chắc tỉ số tăng. Đó là lý do một DP/greedy "cộng dồn" thông thường không áp dụng trực tiếp được.

Bài minh hoạ xuyên suốt trang này là Đề thi (exampick): chọn tập con khác rỗng các bài, sao cho mọi $P$ vị trí liên tiếp có ít nhất một bài được chọn (ràng buộc phủ), và trung bình độ khó lớn nhất.

Ý tưởng Dinkelbach

Mấu chốt: thay vì hỏi "trung bình lớn nhất là bao nhiêu", ta hỏi câu dễ kiểm tra hơn:

Với ngưỡng $\lambda$ cho trước, có tồn tại lời giải hợp lệ với trung bình $\ge \lambda$ không?

Trung bình của $S$ đạt $\ge \lambda$ khi và chỉ khi

$$\frac{{\sum }_{i\in S}{a}_i}{|S|}\ge \lambda ⟺\sum _{i\in S}(a_i-\lambda )\ge 0.$$

Phép trừ $\lambda$ đã gỡ mẫu số ra khỏi tỉ số: giờ mỗi phần tử được chọn đóng góp một trọng số độc lập $w_i=a_i-\lambda$, và ta chỉ cần tối đa hoá tổng trọng số, một bài toán tuyến tính giải được bằng DP/greedy. Đặt

$$g(\lambda )={max}_{S\text{ hợp lệ}}\sum _{i\in S}(a_i-\lambda ).$$

Hàm $g(\lambda )$ có tính chất đẹp:

• Nghịch biến theo $\lambda$ (tăng $\lambda$ thì mọi trọng số giảm).
• $g(\lambda )>0\Rightarrow$ tồn tại tập có trung bình $>\lambda$, nên đáp án tối ưu ${\lambda }^{\backslash }*>\lambda$.
• $g(\lambda )<0\Rightarrow$ mọi tập đều có trung bình $<\lambda$, nên ${\lambda }^{\backslash }*<\lambda$.
• $g({\lambda }^{\backslash }*)=0$ tại đúng đáp án.

Vậy ta chỉ cần tìm nghiệm ${\lambda }^{\backslash }*$ của phương trình $g(\lambda )=0$.

Dinkelbach chính là Newton trên $g$

Có thể chặt nhị phân $\lambda$, nhưng Dinkelbach nhanh hơn nhiều nhờ tận dụng luôn tập tối ưu tìm được:

1. Bắt đầu từ một lời giải hợp lệ bất kỳ, đặt $\lambda ={\displaystyle \frac{\text{sumA}}{\text{cnt}}}$ (trung bình của nó).
2. Giải bài con: tìm tập $B$ tối đa hoá ${\sum }_{i\in B}(a_i-\lambda )$, được giá trị $g(\lambda )$.
3. Nếu $g(\lambda )>0$: tập $B$ có trung bình cao hơn $\lambda$ (vì $\sum (a_i-\lambda )>0$). Cập nhật $\lambda \leftarrow {\displaystyle \frac{{\sum }_{i\in B}{a}_i}{|B|}}$ rồi lặp lại.
4. Nếu $g(\lambda )=0$: không cải thiện được nữa, $\lambda$ hiện tại chính là ${\lambda }^{\backslash }*$. Dừng.

Mỗi vòng $\lambda$ tăng ngặt và tiến về ${\lambda }^{\backslash }*$ với tốc độ siêu tuyến tính (giống Newton), nên thực nghiệm chỉ cần khoảng $\le 20$ vòng ngay cả với dữ liệu lớn.

Ví dụ chạy tay: vòng lặp Dinkelbach

Xét ví dụ 1 của exampick: $n=8$, $P=3$, $a=[1,2,3,4,5,6,7,8]$ (đánh số từ 1).

Khởi tạo bằng một cách phủ hợp lệ: các vị trí $P,2P,\dots$ tức $\{3,6\}$, trung bình $\lambda =4.5$.

Đáp án: tập $\{3,6,7,8\}$, trung bình $6$. Để ý cách $\lambda$ leo dốc $4.5\to 5.8\to 6.0$ và chốt chỉ sau 3 vòng.

Bài con: DP + hàng đợi đơn điệu

Còn lại là giải bài con "tối đa $\sum (a_i-\lambda )$ dưới ràng buộc phủ". Ràng buộc phủ (không có $P$ vị trí liên tiếp cùng bị bỏ) tương đương ba điều kiện về các vị trí được chọn:

• Bài chọn đầu tiên có chỉ số $\le P$ (không thì đầu dãy có $\ge P$ ô trống).
• Bài chọn cuối cùng có chỉ số $\ge n-P+1$.
• Hai bài chọn liên tiếp $j<i$ thoả $i-j\le P$, tức $j\ge i-P$.

Đặt $dp[i]$ = tổng trọng số lớn nhất của một cách phủ hợp lệ đoạn $[1..i]$ với bài $i$ được chọn:

$$dp[i]=(a_i-\lambda )+max(\underset{i\le P}{\underbrace{0}},{max}_{i-P\le j\le i-1}dp[j]).$$

Số hạng $0$ ứng với trường hợp $i$ là bài đầu tiên (chỉ hợp lệ khi $i\le P$). Đáp án bài con là ${max}_{n-P+1\le i\le n}dp[i]$. Truy vết cha để dựng lại tập.

Phần ${max}_{i-P\le j\le i-1}dp[j]$ là cực đại trên cửa sổ trượt độ rộng $P$, xử lý bằng hàng đợi đơn điệu (monotonic deque): duy trì các chỉ số $j$ có $dp[j]$ giảm dần; đầu deque luôn là vị trí cho $dp$ lớn nhất trong cửa sổ. Nhờ đó mỗi lần chạy DP là $O(n)$ thay vì $O(nP)$.

Chạy tay bài con (vòng 2, $\lambda =5.8$)

Dùng mẹo số nguyên (giải thích ở dưới): nhân trọng số với $\text{cnt}=5$, thành $w_i=5a_i-29$. Với $a=[1.\mathrm{.8}]$:

i     1    2    3    4    5    6    7    8
w_i  -24  -19  -14   -9   -4    1    6   11      (= 5*a_i - 29)

Điền $dp$ với $P=3$ (cửa sổ 3 phần tử trước đó; $i\le 3$ được phép làm bài đầu, base $=0$):

Vị trí cuối hợp lệ là $i\ge n-P+1=6$: giá trị lớn nhất là $d{p}_8=4>0$. Truy vết cha $8\to 7\to 6\to 3\to$ đầu, cho tập $\{3,6,7,8\}$. Vì $g>0$ nên cập nhật trung bình lên $6$ và sang vòng sau.

Cài đặt

#include <bits/stdc++.h>
using namespace std;

int n, P;
vector<long long> a;

// Maximize sum of w_i = cnt * a_i - sumA over all valid covers (chosen
// positions with consecutive gaps <= P, first <= P, last >= n - P + 1).
// This is the Dinkelbach subproblem: with lambda = sumA / cnt the weight is
// cnt * (a_i - lambda). Returns the best value and fills bestSet.
static long long dp_solve(long long cnt, long long sumA, vector<int>& bestSet) {
    const long long NEG = LLONG_MIN / 4;      // "unreachable" sentinel
    vector<long long> dp(n + 1, NEG);
    vector<int> par(n + 1, -2);
    deque<int> dq;                            // indices j with dp[j] decreasing
    long long best = NEG;
    int bestEnd = -1;
    for (int i = 1; i <= n; i++) {
        while (!dq.empty() && dq.front() < i - P)   // drop out-of-window
            dq.pop_front();
        long long startCand = (i <= P) ? 0 : NEG;   // i can be the first chosen
        long long base;
        int pj;
        if (!dq.empty() && dp[dq.front()] >= startCand) {
            base = dp[dq.front()];
            pj = dq.front();
        } else {
            base = startCand;
            pj = -1;                          // -1 marks "i is the first chosen"
        }
        if (base <= NEG / 2) {                // no valid way to reach i
            dp[i] = NEG;
            par[i] = -2;
        } else {
            dp[i] = base + cnt * a[i] - sumA;
            par[i] = pj;
            while (!dq.empty() && dp[dq.back()] <= dp[i])  // keep deque decreasing
                dq.pop_back();
            dq.push_back(i);
        }
        if (i >= n - P + 1 && dp[i] > best) { // valid last position
            best = dp[i];
            bestEnd = i;
        }
    }
    bestSet.clear();
    for (int cur = bestEnd; cur != -1; cur = par[cur])
        bestSet.push_back(cur);
    reverse(bestSet.begin(), bestSet.end());
    return best;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n >> P;
    a.assign(n + 1, 0);
    for (int i = 1; i <= n; i++)
        cin >> a[i];

    // Start from any valid cover: positions P, 2P, 3P, ...
    vector<int> S;
    for (int i = P; i <= n; i += P)
        S.push_back(i);
    long long sumA = 0;
    for (int i : S) sumA += a[i];
    long long cnt = (long long)S.size();

    // Dinkelbach: keep raising the average until no cover beats it.
    while (true) {
        vector<int> B;
        long long V = dp_solve(cnt, sumA, B);
        if (V > 0) {                          // found a strictly better average
            sumA = 0;
            for (int i : B) sumA += a[i];
            cnt = (long long)B.size();
            S = B;
        } else {
            break;                            // g(lambda) == 0: optimal reached
        }
    }

    cout << S.size() << "\n";
    for (size_t i = 0; i < S.size(); i++)
        cout << S[i] << " \n"[i + 1 == S.size()];
    return 0;
}

Độ phức tạp

• Thời gian: mỗi vòng Dinkelbach chạy DP + deque hết $O(n)$ (mỗi chỉ số vào/ra deque đúng một lần). Số vòng lặp nhỏ (siêu tuyến tính, thực nghiệm $\le ~20$), nên tổng thể gần $O(n)$. So với chặt nhị phân $\lambda$ mất $O(n\log \frac{V}{\epsilon })$, Dinkelbach vừa nhanh vừa không cần chọn epsilon.
• Bộ nhớ: $O(n)$ cho mảng $dp$, mảng cha và deque.

Mẹo số nguyên (tránh sai số thực)

Vì $\lambda =\text{sumA}/\text{cnt}$ là phân số, nếu tính $a_i-\lambda$ bằng double sẽ có sai số và điều kiện $g(\lambda )>0$ có thể sai ở ngưỡng. Cách chuẩn: nhân toàn bộ trọng số với cnt:

$$\text{cnt}·(a_i-\lambda )=\text{cnt}·a_i-\text{sumA}=w_i\in \mathbb{Z}.$$

Nhân với số dương cnt không đổi dấu tổng, nên $g(\lambda )>0$ tương đương $\sum w_i>0$ trên số nguyên, hoàn toàn chính xác. Kết quả trả về là trung bình lớn nhất đúng tuyệt đối.

⚠️ Lỗi thường gặp

• Bỏ qua ràng buộc phủ, chỉ lấy phần tử lớn nhất. Tối ưu tỉ số "không ràng buộc" của bài này là chọn đúng một bài khó nhất, nhưng nó gần như luôn vi phạm điều kiện phủ $\Rightarrow$ WA. Bài con phải giữ nguyên ràng buộc; Dinkelbach chỉ đổi hàm mục tiêu, không nới miền hợp lệ.
• Nhầm "phủ ít nhất" với "trung bình lớn nhất". In ra một cách phủ cỡ nhỏ nhất (các vị trí $P,2P,\dots$) không hề tối đa trung bình; nó chỉ trùng đáp án khi mọi cách phủ có cùng trung bình. Cách phủ khởi tạo chỉ là điểm xuất phát của Dinkelbach, không phải kết quả.
• DP quét cả cửa sổ $\Rightarrow$ TLE. Nếu tại mỗi $i$ duyệt hết $j\in [i-P,i-1]$ thì mỗi vòng là $O(nP)$; với $P\approx n/2$ thành $~n^2/2$, quá chậm. Bắt buộc dùng deque để lấy cực đại cửa sổ trong $O(1)$ khấu hao.
• Tính trọng số bằng double. Sai số nổi khiến so sánh $g(\lambda )>0$ chập chờn ở biên, cho đáp án lệch 1 phần tử. Dùng mẹo số nguyên $w_i=\text{cnt}·a_i-\text{sumA}$.
• Tràn số. $\text{cnt}\le n\le {10}^5$ và $a_i\le {10}^8$ nên $w_i$ và tổng $dp$ có thể tới $~{10}^{13}$: phải dùng long long cho $dp$, sumA, và giá trị NEG.
• Quên điều kiện biên đầu/cuối. Bài đầu phải $\le P$, bài cuối phải $\ge n-P+1$. Bỏ điều kiện cuối (chỉ lấy $max$ trên toàn bộ $dp$) sẽ cho tập kết ở giữa dãy, để lộ $\ge P$ ô trống ở đuôi.
• Điều kiện dừng sai. Phải dừng khi $g(\lambda )=0$ (không cải thiện), không phải khi $g(\lambda )<0$. Nếu lỡ dùng >= 0 để tiếp tục thì lặp vô hạn tại nghiệm.

Biến thể và mở rộng

Dinkelbach là khuôn mẫu chung cho mọi bài "tối ưu tỉ số" khi bài con tuyến tính hoá giải được nhanh:

• Chặt nhị phân trên đáp số là lựa chọn thay thế: nhị phân $\lambda$, mỗi bước kiểm tra $g(\lambda )\ge 0$. Dễ cài hơn nhưng chậm hơn và phải xử lý epsilon; xem Tìm kiếm nhị phân trên đáp số.
• Chu trình tỉ lệ nhỏ nhất (minimum mean cycle): tìm chu trình cực tiểu $\frac{\sum w_e}{\text{số cạnh}}$; bài con là dò chu trình âm với trọng số $w_e-\lambda$ (Bellman-Ford), hoặc thuật toán Karp.
• Đồ thị con mật độ cao nhất (maximum density subgraph): cực đại $\frac{|E^{\prime }|}{|V^{\prime }|}$; bài con quy về luồng cực đại / lát cắt nhỏ nhất với tham số $\lambda$.
• Bài toán vận tải / phân số tuyến tính tổng quát: cùng công thức $g(\lambda )=max(f(S)-\lambda h(S))$ miễn là $h(S)>0$ và bài con giải được.

Điểm chung: nhận diện tỉ số hai đại lượng cùng phụ thuộc lời giải, rồi kiểm tra bài con "trừ $\lambda$" có giải nhanh không.

Bài tập luyện

• Cửa Sổ Phép Thuật (slidewin) — (Trung cấp) làm chủ cực đại cửa sổ trượt bằng deque, chính là chương trình con lõi của DP ở đây.
• Tỷ lệ thành công (succrate) — (Nâng cao) tư duy tỉ số và chặt nhị phân trên đáp số, làm quen với việc "trừ ngưỡng" để kiểm tra một tỉ lệ.
• Bức ảnh Gold (photogold) — (Kỳ cựu) đúng khuôn DP + monotonic deque dạng $dp[i]=w_i+max$ cửa sổ, luyện phần bài con của Dinkelbach.
• Vũ Điệu Cầu Thang (gridwaltz) — (Kỳ cựu) DP tối ưu bằng deque ở mức khó hơn, siết kỹ năng cài đặt cửa sổ trượt cho quy hoạch động.
• Đề thi (exampick) — (Rất khó) bài tổng hợp: ghép Dinkelbach + DP phủ + deque + mẹo số nguyên thành một lời giải hoàn chỉnh.