【每周一题】2017.3.6 HDU1009 解题报告

题目描述

• 杰瑞有M磅猫粮，他可以用猫粮跟仓库里每个房间的猫咪换取奶酪。假设仓库有N个房间，第i个房间有J[i]磅奶酪，看守这个房间的猫需要F[i]磅猫粮。杰瑞不需要换取某个房间中的所有奶酪，它可以用F[i]*a%的猫粮换取J[i]*a%的猫粮（a是一个实数）。请你帮杰瑞算出它最多能获取多少磅奶酪。【提示：请参考经典算法中的<部分背包问题>】
• 可以把代码提交至这里：http://acm.hdu.edu.cn/showproblem.php?pid=1009

解题分析

• 这道题是一个非常典型的贪心算法题。贪心算法（又称贪婪算法）是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的是在某种意义上的局部最优解。如何粗略判断一道题是否为贪心算法？很简单，只要看题目中选择物体的时候，是可以选取一部分，还是必须整个物体都要选。如果是选取部分，那么就是贪心算法；如果整个物体都要选，那么就是动态规划算法（请参考01背包问题）。

• 那么这道题很显然了——“杰瑞不需要换取某个房间中的所有奶酪，它可以用F[i]*a%的猫粮换取J[i]*a%的猫粮”，因此是一个贪心算法题。我们只需要求出每个房间的性价比（即用奶酪除以猫粮），然后把每个房间的性价比按照从大到小排序，逐个换取。如果最后剩余的猫粮不足以换取一整个房间的奶酪，那么这个房间换取部分奶酪就可以了。

• 几个需要注意的地方：

  1. 有多个输入数据，以“-1 -1”为结尾。
  2. float不一定够用，尝试double。（你能想出一个使用float得到错误答案的输入数据吗？）
  3. 要考虑到特殊情况，比如猫粮可能用不完。

• 贪心算法是经典算法，请熟练掌握。

思考题

1. 这道题的时间复杂度和空间复杂度是多少？

2. 如果把题意改成“杰瑞必须换取房间中的所有奶酪，不能换取一部分”，那么这是一道什么算法题？

例程（C++）

（注：例程只是给出一种解题方法，不是标准程序，也不一定是最完美的解法）

//HDU 1009 by Xinjie Wang

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

typedef struct DATASET
{
    int JavaBeans;
    int CatFood;
    double JavaBeansPerCatFood;
}DataSet;

bool compareFunc(DataSet _a, DataSet _b)
{
    return _a.JavaBeansPerCatFood > _b.JavaBeansPerCatFood;
}

int main()
{
    int m, n;
    while (scanf("%d %d", &m, &n), (m!= -1) && (n != -1))
    {
        DataSet dataset[1024];
        int J, F;
        for (int i = 0; i < n; i++)
        {
            cin >> J >> F;
            dataset[i].JavaBeans = J;
            dataset[i].CatFood = F;
            dataset[i].JavaBeansPerCatFood = J / (double)F;
        }
        
        sort(dataset, dataset + n, compareFunc);

        double finalAmount = 0;
        for (int i = 0; i < n; i++)
        {
            if (m >= dataset[i].CatFood)
            { 
                m -= dataset[i].CatFood;
                finalAmount += dataset[i].JavaBeans;
            }
            else
            {
                finalAmount += m * dataset[i].JavaBeansPerCatFood;
                break;
            }
        }

        printf("%.3f\n", finalAmount);
    }
    return 0;

}