算法笔记简单贪心（月饼问题）

た入场券 2022-06-01 10:08 215阅读 0赞

\*\*

## 概念 ##

\*\*  
贪心法是求解一类最优问题的方法，它总是考虑当前状态下局部最优（或较优）的策略，来使全局的结果达到最优（或较优）。显然，如果采取较优而非最优的策略（最优策略可能不存在或是不易想到），得到的全局结果也无法是最优的。而要获得最优结果，则要求中间的每步策略都是最优的，因此严谨使用贪心法来求解最优化问题需要对采取的策略进行证明。证明的一般思路是使用反证法和数学归纳法，即假设策略不能导致最优解，然后通过一系列推导来得到矛盾，以此证明策略是最优的。不过对平常使用来说，也许没有时间或者不太容易对想到的策略进行严谨的证明（贪心的证明往往比贪心本身更难），因此一般来说，**如果在想到某个似乎可行的策略，并且自己无法举出反例，那么就勇敢的实现它。**

例1：月饼

题目描述

> 月饼是中国人在中秋佳节时吃的一种传统食品，不同地区有许多不用风味的月饼。现给定所有种类月饼的库存量，总售价以及市场的最大需求量，试计算可以获得的最大收益是多少。  
> 注意：销售时允许取出一部分库存。样例给出的情形是这样的：假如有三种月饼，其库存量分别为18，15，10万吨，总售价分别为75，72，45亿元。如果市场的最大需求量只有20万吨，那么最大收益策略应该是卖出全部的15万吨第二种月饼以及5万吨第三种月饼，获得72+45/2=94.5（亿元）。

输入格式

> 每个输入包含1个测试用例。每个测试用例先给出一个不超过1000的正整数N表示月饼的种类数以及不超过500（以万吨为单位）的正整数D表示市场最大需求量；随后一行给出N个正数表示每种月饼的库存量（以万吨为单位）；最后一行给出N个正数表示每种月饼的总售价（以亿元为单位）。数字间以空格分割。

输出格式

> 对每组测试用例，在一行中输出最大收益，以亿元为单位并精确到小数点后两位。

输入样例

> 3 20  
> 18 15 10  
> 75 72 45

输出样例

> 94.50

题意

> 现有月饼需求量为D，已知n种月饼各自的库存量和总售价，问如何销售这些月饼，使得可以获得的受益最大。求最大收益。

思路

> 步骤1：这里采用“总是选择单价最高的月饼出售，可以获得最大的利润”的策略。  
> 因此，对每种月饼，都根据起库存量和总售价来计算出该种月饼的单价。  
> 之后，将所有月饼按单价从高到低排序。  
> 步骤2：从单价高的月饼开始枚举。  
> ①如果该种月饼的库存量不足以填补所有的需求量，则将该种月饼全部卖出，此时需求量减少该种月饼的库存量大小，收益值增加该种月饼的总售价大小。  
> ②如果该种月饼的库存量足够供应需求量，则只提供需求量大小的月饼，此时收益值增加当前需求量乘以该种月饼的单价，而需求量减为0.  
> 这样，最后得到的收益值即为所求的最大收益值。  
> **策略正确性的证明：**假设有两种单价不同的月饼，其单价分别为a和b(a < b)。如果当前需求量为K，那么两种月饼的总收入分别为aK和bK，而aK < bK显然成立，因此需要出售单价更高的月饼。

注意点

> ①月饼库存量和总售价可以是浮点数（题目中只说是正数，没说是正整数），需要用double型存储。对于，总需求量D虽然题目说是正整数，但是为了后面计算方便，也需要定义为浮点型。很多得到“答案错误”的代码都错在这里。  
> ②当月饼库存量高于需求量时，不能先令需求量为0，然后再计算收益，这会导致该步收益为0。  
> ③当月饼库存量高于需求量时，要记得将循环中断，否则会出错。

参考代码

#include<cstdio>
    #include<algorithm>
    using namespace std;
    struct mooncake{
        double store;//库存量
        double sell;//总售价
        double price;//单价
    }cake[1010];
    bool cmp(mooncake a,mooncake b){
       //按单价从高到低排序
        return a.price > b.price;
    }
    int main(){
        int n;
        double D;
        scanf("%d%lf",&n,&D);
        for(int i = 0;i < n; i++){
            scanf("%lf",&cake[i].store);
        }
        for(int i = 0;i < m; i++){
            scanf("%lf",&cake[i].sell);
            cake[i].price = cake[i].sell / cake[i].store;//计算单价
        }
        sort(cake,cake + n,cmp);//单价从高到低排序
        double ans = 0;//收益
        for(int i = 0;i < n;i ++){
            if(cake[i].store <= D){
       //如果需求量高于月饼库存量
                D -= cake[i].store;//第i种月饼全部卖出
                ans += cake[i].sell;
            }else{
       //如果月饼库存量高于需求
                ans += cake[i].price * D;//只卖出剩余需求量的月饼
                break;
            }
        }
        printf("%.2f\n",ans);
        return 0;
    }

> 摘自《算法笔记》胡凡，曾磊主编