JavaBean 最优兑换策略：贪心算法解决 FatMouse 的猫粮交易问题

问题描述：

一只名为 FatMouse 的老鼠非常喜欢 JavaBean，他准备了 M 磅猫粮，想要从 N 个房间的猫手中换取 JavaBean。每个房间都有不同数量的 JavaBean (J[i]) 和所需的猫粮 (F[i])，FatMouse 可以选择部分兑换，即用 F[i] * a% 的猫粮换取 J[i] * a% 的 JavaBean (a 为实数)。现在，你需要帮助 FatMouse 计算出他能获得的最大 JavaBean 数量。

输入格式:

多组测试数据。每组数据以一行包含两个非负整数 M 和 N 开始，分别表示猫粮总量和房间数量。接下来 N 行，每行包含两个非负整数 J[i] 和 F[i]，分别表示第 i 个房间的 JavaBean 数量和所需猫粮数量。最后以一行包含两个 -1 的数据结束输入。所有整数都不大于 1000。

输出格式:

对于每组测试数据，输出一行，包含一个保留三位小数的实数，表示 FatMouse 能获得的最大 JavaBean 数量。

解题思路:

本题可以使用贪心算法解决。为了使获得的 JavaBean 最多，我们需要优先选择性价比最高的房间进行兑换，即单位猫粮可以兑换最多 JavaBean 的房间。

算法步骤:

计算每个房间的性价比，即 J[i] / F[i]。2. 按照性价比从高到低对房间进行排序。3. 从性价比最高的房间开始，如果剩余猫粮足够兑换该房间的所有 JavaBean，则全部兑换；否则，兑换尽可能多的 JavaBean。4. 重复步骤 3，直到猫粮用完或所有房间都已兑换完毕。

**代码实现 (C语言):**c// 由于无法提供代码，以下代码仅供参考#include <stdio.h>#include <stdlib.h>

typedef struct { int j; // JavaBean 数量 int f; // 所需猫粮 double ratio; // 性价比} Room;

int cmp(const void *a, const void *b) { Room *ra = (Room *)a; Room *rb = (Room *)b; return (rb->ratio - ra->ratio > 0) ? 1 : -1;}

int main() { int m, n, i; double result; Room rooms[1000]; while (scanf('%d %d', &m, &n) != EOF) { if (m == -1 && n == -1) { break; } for (i = 0; i < n; i++) { scanf('%d %d', &rooms[i].j, &rooms[i].f); rooms[i].ratio = (double)rooms[i].j / rooms[i].f; } qsort(rooms, n, sizeof(Room), cmp); result = 0; for (i = 0; i < n; i++) { if (m >= rooms[i].f) { result += rooms[i].j; m -= rooms[i].f; } else { result += rooms[i].ratio * m; break; } } printf('%.3lf ', result); } return 0;}

总结:

本文介绍了如何使用贪心算法解决 FatMouse 的猫粮交易问题，并提供了 C 语言代码实现。