8、算法：贪心算法

有m元钱，n中物品；每种物品有j磅，总价值f元，可以使用0到f的任意价格购买相应磅的物品，例如使用0.3f元，可以购买0.3j磅物品。要求输入用m元钱最多能买到多少物品。

#include <iostream>
#include <algorithm>
#include <iomanip>
using namespace std;

struct goods{ // 表示可买物品的结构体
    double j; // 该物品总重
    double f; // 该物品总价值
    double s; // 该物品性价比
    bool operator < (const goods &A) const{ //重载小于运算符
      return s>A.s; // sort默认从小到大排序（正常return s<A.s），如果return s>A.s相当于从大到小排序
    }
}good[1000];

int main(){
  double m;
  int n;
  while(scanf("%lf%d", &m,&n) != EOF){
        if(m==-1 && n==-1) break; // 当m==-1 && n==-1时跳出循环，程序运行结束
        for (int i = 0; i < n; ++i) {
      scanf("%lf%lf", &good[i].j, &good[i].f);
      good[i].s = good[i].j / good[i].f;
    }

        // 第三个参数：less<int>从小到大；greater<int>从大到小；greater<char>
        // 快排，时间复杂度为n*log2(n)
        sort(good, good+n);

        int idx = 0;
        double ans = 0;

        while(m>0 && idx<n){
          if(m>good[idx].f){
            ans += good[idx].j;
            m -= good[idx].f;
          }else {
            ans += m*good[idx].s;
            m = 0;
      }
          idx++;
        }

//        printf("%.3lf\n", ans);
        cout << setiosflags(ios::fixed) << setprecision(3) << ans <<endl;
  }

  return 0;
}