NYoj 914 - 二分答案 + 貪心選擇最大化單位重量價值

問題描述

N 件物品 (N ≤ 10000)，每件有重量 W_i 和價值 V_i。選擇恰好 K 件 (K ≤ N)，使 單位重量價值 (ΣV) / (ΣW) 最大。輸出最大值 (保留兩位小數)。

核心洞察：二分答案 + 判定可行性

設最大平均值為 X。對於候選值 mid，判定是否存在 K 件物品使 (ΣV)/(ΣW) ≥ mid ⇔ Σ(V - mid·W) ≥ 0。

定義調整值 a_i = V_i - mid * W_i。選 K 件使和最大 → 貪心選擇最大的 K 個 a_i。若前 K 大之和 ≥ 0，說明 mid 可行，可增大；否則縮小。

算法流程

1. 二分範圍：low = 0, high = max(V_i/W_i) (單件最大平均值為上界)。
2. 迭代直到 high - low < 1e-5 (保證兩位小數正確)。
3. 判定函數 check(mid)：
   • 計算所有 a_i = V_i - mid * W_i。
   • 降序排序 a_i。
   • 求前 K 項和 sum。
   • 返回 sum >= 0。
4. 輸出 low (或 high) 保留兩位小數。

為什麼直接貪心選最大 V/W 失敗？

樣例：3 件選 2 件。
(2,2) → 1.0
(5,3) → 0.6
(2,1) → 0.5
直接選前兩大 V/W (1.0 和 0.6) 得總價值 5、總重量 7 → 平均 0.714。
但選 (2,2) 和 (2,1) 得 總價值 3、總重量 4 → 平均 0.75 更大。
原因：平均值非線性，組合效應導致局部最優 ≠ 全局最優。

參考代碼

#include <bits/stdc++.h>
using namespace std;
const double EPS = 1e-5;

struct Item { double w, v; } items[10005];
double adjusted[10005];
int n, k;

bool check(double mid) {
    for (int i = 0; i < n; i++)
        adjusted[i] = items[i].v - mid * items[i].w;
    sort(adjusted, adjusted+n, greater());
    double sum = 0;
    for (int i = 0; i < k; i++) sum += adjusted[i];
    return sum >= 0;
}

int main() {
    while (scanf("%d%d", &n, &k) == 2) {
        double hi = 0;
        for (int i = 0; i < n; i++) {
            scanf("%lf%lf", &items[i].w, &items[i].v);
            hi = max(hi, items[i].v / items[i].w);
        }
        double lo = 0;
        while (hi - lo > EPS) {
            double mid = (lo + hi) / 2;
            if (check(mid)) lo = mid;
            else hi = mid;
        }
        printf("%.2lf\n", lo);
    }
    return 0;
}

複雜度

• 二分迭代 ~30 次 (log₂(1e5/1e-5) ≈ 33)。
• 每次判定：O(N log N) 排序 (N=10000)。
• 總 O(30·N log N) ≈ 400萬操作，極快。
• 可優化：用 nth_element 選前 K 大 O(N)，但排序常數小且代碼簡單。