FatMouse' Trade：貪心策略解決分數背包問題

題目大意

貓鼠有 M 磅貓糧，倉庫 N 個房間，第 i 房有 J[i] 磅 JavaBean，需 F[i] 磅貓糧可全換。可部分交易：付 a% 貓糧得 a% JavaBean。求最大獲得 JavaBean 量（保留 3 位小數）。

貪心證明

單位貓糧換得 JavaBean 比率 rate = J[i]/F[i]。為使總量最大，應優先選擇 rate 最高的房間完整交易，貓糧不足時按比例部分交易。此為分數背包問題標準貪心解，最優子結構顯然成立。

完整代碼 (C++)

#include <cstdio>
#include <algorithm>
struct Room { int J, F; double rate; } r[1005];

bool cmp(const Room& a, const Room& b) {
    return a.rate > b.rate;
}

int main() {
    int M, N;
    while (scanf("%d%d", &M, &N) == 2) {
        if (M==-1 && N==-1) break;
        for (int i=0;i0;++i) {
            if (M >= r[i].F) { M -= r[i].F; ans += r[i].J; }
            else { ans += r[i].rate * M; M = 0; }
        }
        printf("%.3f\n", ans);
    }
    return 0;
}

關鍵細節

• rate 用 double 避免整數除法截斷。
• 排序比較函式處理 rate 相等情況（可按 J 大小或不處理）。
• 輸出格式 %.3f 自動四捨五入保留三位小數。

複雜度

• 時間 O(N log N)（排序主導），空間 O(N)。

總結

FatMouse' Trade 是分數背包問題的教科書級例題。貪心策略直觀且最優，代碼極短，適合作為貪心算法入門講解與練習題。