【贪心】FatMouse‘s Trade

老鼠准备了 M 磅猫粮，并且准备拿这些猫粮和仓库的猫交换咖啡豆。

仓库有 N 个房间（都有咖啡豆）。在第i个房间内有 J[i] 磅咖啡豆，但相应地需要付出 F[i] 磅的猫粮才能进行兑换。但是，老鼠不一定要兑换该房间内全部的咖啡豆；相反，如果老鼠支付 a%*F[i] 的猫粮，那么可以获得 a%*J[i] 的咖啡豆。现在请你计算 M 磅猫粮最多可以获得多少咖啡豆。

输入数据有多组。每组数据包括第一行：M N，接下来是N行，每行包含两个非负整数 J[i] F[i]。最后一组数据为 -1 -1，表示结束。

每组数据输出一行，仅有一个带三位小数的数据，代表最大数量的咖啡豆.

5 3 7 2 4 3 5 2 20 3 25 18 24 15 15 10 -1 -1 【样例输出】

13.333 31.500 【分析】

①.不断买性价比（重量价格之比）最高的物品。若当前性价比最高的物品已被买完，则继续在剩余的物品中寻找性价比最高的物品，不断重复这个过程。

②.若当前金钱耗尽，则代表交易结束；此时，已经买到了最多的物品。

（本题中，每个房间的咖啡豆对应于不同的商品，每个房间的 J[i] 代表该商品的重量，F[i] 代表该商品的价格，老鼠手中的猫粮对应于金钱。）

#include<iostream>

#include<cstdio>

#include<algorithm>

using namespace std;

const int MAX=1000;

struct JavaBean{

double weight;

double cost;

};

JavaBean arr[MAX];

bool Compare(JavaBean x,JavaBean y)

{

return (x.weight/x.cost)>(y.weight/y.cost);

}

int main()

{

int m,n;

while(cin>>m>>n)

{

if(m==-1&&n==-1)

break;

for(int i=0;i<n;i++)

cin>>arr[i].weight>>arr[i].cost;

sort(arr,arr+n,Compare);

double answer=0;

for(int i=0;i<n;i++)

{

if(m>=arr[i].cost)

{

m-=arr[i].cost;

answer+=arr[i].weight;

}

else

{

answer+=arr[i].weight*(m/arr[i].cost);

break;

}

}

printf("%.3fn",answer);

}

return 0;

}

相关知识

hdu 1009 FatMouse'Trade （贪心算法）
贪心之老鼠与猫的交易（详细分析）
德国纽伦堡国际宠物用品展览会International Trade Fair for Pet Supplies
猫咪免费领养套路❗️别被贪心蒙了眼
焦点分析｜连锁食品超市 Trader Joe's 创始人去世，其开创的自有品牌模式依旧无人能超越
看看杜鹃幼鸟有多么贪心，把手放它背上还想把我推走！
2025年日本东京装饰宠物用品展 2024
2025年日本东京装饰宠物用品展 视频
Stella & Chewy's
美国特色小礼物推荐

网址: 【贪心】FatMouse‘s Trade https://www.mcbbbk.com/newsview349876.html