简单贪心

可以买一部分的,求最值问题 eg.背包问题

老鼠准备了M磅猫粮，并且准备拿这些猫粮和守卫仓库的猫交换自己最爱的咖啡豆 （JavaBean）。仓库共有N个房间，每个房间里面都有咖啡豆。在第i个房间内有J[i]磅咖啡豆， 但相应地需要付出F[i]磅的猫粮才能进行兑换。但是，老鼠并不一定要兑换该房间内全部的咖 啡豆；相反，如果老鼠支付a%*F[i]的猫粮，那么可以获得a%*J[i]的咖啡豆。现在请你告诉它， M磅猫粮最多可以获得多少咖啡豆

#define _CRT_SECURE_NO_WARNINGS

#include <iostream>

#include <cstdio>

#include <algorithm>

using namespace std;

const int maxn = 1000;

struct javabean {

double weight;

double cost;

};

javabean arr[maxn];

bool compare(javabean x, javabean y) {

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

}

int main() {

int m, n; //M磅猫粮 N个房间

while (scanf("%d%d", &m, &n) != EOF) {

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

break;

}

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

scanf("%lf%lf", &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("%.3f\n", answer);

}

return 0;

}