贪心类算法总结

骑猪看日落 2023-07-24 02:38 12阅读 0赞

# 例题： #

输入描述：  
有多组测试数据。  
第一行输入两个非负整数x 和n。  
接下来n 行，每行输入两个整数，分别为mi 和wi。  
所有数据都不大于1000。  
x 和n 都为-1 时程序结束。  
输出描述：  
请输出小明最多能喝到多少毫升的饮料，结果保留三位小数。  
输入样例\#:  
233 6  
6 1  
23 66  
32 23  
66 66  
1 5  
8 5  
\-1 -1  
输出样例\#:  
136.000

代码：

#include <bits/stdc++.h>
    #define N 1000
    using namespace std;
    struct drink
    {
        double w,m;
    }d[N];
    bool cmp(drink a, drink b)
    {
        return a.w/a.m < b.w/b.m; // 从小到大排序
    }
    int main()
    {
       int n=0,x=0; // X元，n种饮料
       while(cin>>x>>n)
       {
            if(x==-1&&n==-1) break;
            for(int i=0; i<n; i++)
            {
                cin>>d[i].m>>d[i].w;
            }
            sort(d, d+n, cmp);
            double ans = 0;
            for(int i=0; i<n; i++)
            {
                if(x>=d[i].w)
                {
                    ans+=d[i].m;
                    x-=d[i].w;
                }
                else
                {
                    ans+=x*d[i].m/d[i].w;
                    break;
                }
            }
            printf("%.3lf\n", ans);
        }
    	return 0;
    }

求解思路：

通过分析之后我们可以发现，小明想要喝尽量多的饮料的话，肯定优先选择性价比  
最高的饮料喝，也就是说1 毫升的价格最低的饮料先喝，那么我们就需要去比较，每种饮料1  
毫升的价格是多少。然后按照这个单价从低到高依次排序，然后一个一个往后喝，这样可以保  
证小明能喝到最多的饮料。

贪心类算法思路：

解题的通用步骤  
1、建立数学模型来描述问题；  
2、把求解的问题分成若干个子问题；  
3、对每一子问题求解，得到子问题的局部最优解；  
4、把子问题的局部最优解合成原来问题的一个解。