NYOJ 824 Greedy Mouse：分數背包問題與精度處理

題目

老鼠偷吃奶酪：n 種奶酪，每種有價值 x 和重量 y。老鼠能負重 m。可取部分奶酪。求最大總價值。多測資，m=n=-1 結束。

貪心策略

按單位價值 rate = x/y 降序排序。依序取整塊，直到剩餘容量不足，取部分（value += remain * rate）。

精度與細節

• 用 double 存儲 rate 與答案。
• 排序比較函數：return b.rate - a.rate（降序）。
• 輸出保留三位小數 %.3lf。
• 輸入結束條件：while(scanf("%d%d",&m,&n), m!=-1 || n!=-1)。

完整 C 代碼

#include 
#include 

typedef struct { int x, y; double rate; } Node;

int cmp(const void* a, const void* b) {
    Node* p1 = (Node*)a; Node* p2 = (Node*)b;
    if (p1->rate < p2->rate) return 1;
    if (p1->rate > p2->rate) return -1;
    return 0;
}

int main() {
    int m, n;
    while (scanf("%d%d", &m, &n) == 2) {
        if (m == -1 && n == -1) break;
        Node* a = (Node*)malloc(n * sizeof(Node));
        for (int i=0; i0; ++i) {
            if (a[i].y <= m) {
                ans += a[i].x;
                m -= a[i].y;
            } else {
                ans += m * a[i].rate;
                break;
            }
        }
        printf("%.3lf\n", ans);
        free(a);
    }
    return 0;
}

常見錯誤

• 整數除法導致 rate=0：必須轉 double。
• 輸入結束條件判斷錯誤。
• 未釋放動態記憶體（雖然程式結束會自動回收）。