HDU 1.3.1：FatMouse' Trade - 分數背包貪心

問題描述

FatMouse 有 M 磅貓食，N 個房間。第 i 房間有 J[i] 磅 JavaBean，需 F[i] 磅貓食。可按比例交易（買 a% 得 a%）。求最大獲得 JavaBean 量。

貪心策略：單位價值排序

計算每房間「單位貓食換 Bean 率」 rate = J[i] / F[i]。按 rate 降序排序，依次盡可能多買（貓食夠買整間則全買，不夠則按比例買剩餘部分）。

代碼實現

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

struct Room { double j, f, rate; };

int main() {
    double M; int N;
    while (cin >> M >> N, M != -1 || N != -1) {
        vector a(N);
        for (auto &r : a) {
            cin >> r.j >> r.f;
            r.rate = r.j / r.f;
        }
        sort(a.begin(), a.end(), [](Room x, Room y){ return x.rate > y.rate; });
        double ans = 0;
        for (auto &r : a) {
            if (M >= r.f) { ans += r.j; M -= r.f; }
            else { ans += r.rate * M; break; }
        }
        printf("%.3f\n", ans);
    }
    return 0;
}

關鍵點

• 分數背包問題：價值/重量比排序，貪心選擇。
• 輸入以 -1 -1 結束。
• 輸出保留 3 位小數。

總結

最基礎的貪心算法例題：分數背包。證明依賴交換論證——單位價值高的優先裝入總是最優。