洛谷P2095 食品选择：贪心算法C++实现与优化策略

ftggdnt

一、题目解读

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

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

• ‌贪心策略‌：优先选择脂肪含量高的食品
• ‌数据结构‌：
  
  
  • 使用结构体存储食品的脂肪含量和类别
  • 重载运算符实现按脂肪降序排序
    
    
• ‌限制处理‌：通过计数器跟踪每类食品已选数量
  
  

三、解题步骤详解

• ‌输入处理‌：
  
  
  • 读取食品总数n、需要选择数m、类别数k
  • 存储每类食品的**允许选择量
    
    
• ‌数据预处理‌：
  
  
  • 将所有食品按脂肪含量降序排序
    
    
• ‌选择过程‌：
  
  
  • 遍历排序后的食品列表
  • 检查当前食品类别是否已达上限
  • 未达上限则选择该食品
    
    
• ‌结果输出‌：输出所选食品的总脂肪量
  
  

四、完整代码实现#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;
    }
   
    // 读取所有食品信息
    vector<Food> foods(n);
    for(int i = 0; i < n; ++i) {
        cin >> foods.fat >> foods.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.category;
        // 检查类别限制
        if(consumed[cat] < max_per_category[cat]) {
            total_fat += foods.fat;
            consumed[cat]++;
            selected++;
        }
    }
   
    cout << total_fat << endl;
    return 0;
}
五、总结

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

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