【算法详解】洛谷P2095 食品选择问题：贪心算法C++实现与优化策略

一、SEO化题目解读

洛谷P2095是一道典型的资源分配优化问题，要求从n种食品中选择m份，在满足各类食品数量限制的前提下，最大化总脂肪摄入量。题目考察贪心算法的应用能力，是学习算法设计与优化的经典案例。

二、解题思路（参考代码分析）

1. ‌贪心策略‌：优先选择脂肪含量高的食品

2. ‌数据结构‌：

• 使用结构体存储食品的脂肪含量和类别

• 重载运算符实现按脂肪降序排序

3. ‌限制处理‌：通过计数器跟踪每类食品已选数量

三、解题步骤详解

1. ‌输入处理‌：

• 读取食品总数n、需要选择数m、类别数k

• 存储每类食品的最大允许选择量

2. ‌数据预处理‌：

• 将所有食品按脂肪含量降序排序

3. ‌选择过程‌：

• 遍历排序后的食品列表

• 检查当前食品类别是否已达上限

• 未达上限则选择该食品

4. ‌结果输出‌：输出所选食品的总脂肪量

四、完整代码实现

#include <iostream>
#include <vector>
#include <algorithm>
using namespACe std;

// 食品结构体：包含脂肪含量和类别信息
struct Food {
    int fat;      // 脂肪含量
    int category; // 食品类别
    // 重载<运算符实现降序排序
    bool operator<(const Food &f) const {
        return fat > f.fat; // 按脂肪降序排序
    }
};

int main() {
    int n, m, k;
    cin >> n >> m >> k;
    
    // 存储每类食品的最大允许选择量
    vector<int> max_per_category(k+1); 
    for(int i = 1; i <= k; ++i) {
        cin >> max_per_category[i];
    }
    
    // 读取所有食品信息
    vector<Food> foods(n);
    for(int i = 0; i < n; ++i) {
        cin >> foods[i].fat >> foods[i].category;
    }
    
    // 按脂肪含量降序排序
    sort(foods.begin(), foods.end());
    
    // 已消费的各类食品数量统计
    vector<int> consumed(k+1, 0); 
    int total_fat = 0;  // 总脂肪量
    int selected = 0;   // 已选食品数
    
    // 贪心选择过程
    for(int i = 0; i < n && selected < m; ++i) {
        int cat = foods[i].category;
        // 检查类别限制
        if(consumed[cat] < max_per_category[cat]) {
            total_fat += foods[i].fat;
            consumed[cat]++;
            selected++;
        }
    }
    
    cout << total_fat << endl;
    return 0;
}

五、总结

本文详细解析了洛谷P2095食品选择问题的贪心算法解法，通过优先选择高脂肪食品的策略，在满足类别限制的条件下实现了脂肪摄入最大化。该算法时间复杂度为O(nlogn)，主要来自排序操作，适合处理大规模数据。