POJ 2976：0-1 分數規劃 + 二分求最大密度

問題描述

給定 n 對 (a_i, b_i)，最多捨棄 k 對，求剩餘對的 Σa / Σb 最大值。n≤1000。

0-1 分數規劃轉化

設目標最大值為 x。定義 g(x) = max_{選擇} Σ(a_i - x*b_i)。
g(x) 關於 x 單調遞減。
g(x)=0 ⇔ x 為最優值。
二分 x，每次計算 g(x)：對每對算 val = a_i*100 - x*b_i（放大 100 避免浮點），排序取前 n-k 大者求和。若和 ≥ 0 則 x 偏小，增大；否則減小。

代碼實現

struct Node { double a,b; } p[1100];
double c[1100];
int n,k;

double check(double x) {
    for (int i=0;i());
    double sum=0;
    for (int i=0;i=0) l=mid;
            else r=mid;
        }
        printf("%.0f\n", mid+0.5); // 四捨五入輸出整數
    }
    return 0;
}

關鍵點

• 分數規劃核心：max Σa/Σb ⇔ max Σ(a - x*b)=0。
• 每次檢查 O(n log n)，二分 50 次足夠精度。
• 放大 100 倍用 double 避免精度問題，最終四捨五入。
• 最多捨棄 k 對 ⇔ 選擇 n-k 對使 Σ(a-xb) 最大，即取最大的 n-k 個值。

總結

POJ 2976 是「0-1 分數規劃 + 二分」的教科書例題。關鍵在於識別目標函數為比值形式，通過參數化轉化為單調判定函數。此模板廣泛適用於「最大化/最小化比值」且可選擇子集的問題。