登录以参加训练计划

好的！贪心算法就像吃自助餐时每次都选最贵的食物，通过局部最优选择来寻求全局最优解。下面用超多生活案例+图解帮你彻底掌握这个算法~ 🚀

---

🌟 贪心算法核心思想

• 每一步都选当前最好的：就像吃自助餐先拿龙虾
• 不回头：一旦选择就不改变（不像回溯会撤销）
• 高效但需验证：不一定所有问题都适用！

---

✅ 适用贪心的场景

问题特征	示例	是否适用贪心
最优子结构	部分背包问题	✅
无后效性	活动选择问题
贪心选择性质	找零钱（标准币值）
需要全局考虑	0-1背包问题	❌

---

📝 贪心算法解题步骤

1. 问题分解：将大问题拆成多个步骤选择
2. 制定贪心策略：明确每一步的局部最优选择标准
3. 验证正确性：必须证明该策略能得到全局最优
4. 实现算法：通常需要配合排序等预处理

---

🍔 经典例题1：部分背包问题

问题：小偷拿背包容量W，物品可分割，求最大价值
贪心策略：优先拿单位价值最高的物品

struct Item {
    int weight;
    int value;
    double ratio; // value/weight
};

bool compare(Item a, Item b) {
    return a.ratio > b.ratio; // 按单位价值降序排序
}

double fractionalKnapsack(int W, vector<Item>& items) {
    sort(items.begin(), items.end(), compare);
    double totalValue = 0.0;
    
    for(auto& item : items) {
        if(W >= item.weight) { // 全拿
            totalValue += item.value;
            W -= item.weight;
        } else { // 拿部分
            totalValue += W * item.ratio;
            break;
        }
    }
    return totalValue;
}

---

⏰ 经典例题2：活动选择问题

问题：选最多数量的不重叠活动
贪心策略：每次选最早结束的活动，给后面留更多时间

// 活动按结束时间排序
bool compare(pair<int,int> a, pair<int,int> b) {
    return a.second < b.second;
}

int selectActivities(vector<pair<int,int>>& activities) {
    sort(activities.begin(), activities.end(), compare);
    int count = 1;
    int lastEnd = activities[0].second;
    
    for(int i=1; i<activities.size(); i++) {
        if(activities[i].first >= lastEnd) {
            count++;
            lastEnd = activities[i].second;
        }
    }
    return count;
}

---

💰 经典例题3：找零钱问题（标准币值）

问题：用最少硬币找零n元（假设币值1,5,10,20,50,100）
贪心策略：优先用最大面额

vector<int> coins = {100, 50, 20, 10, 5, 1};

vector<int> giveChange(int amount) {
    vector<int> result;
    for(int coin : coins) {
        while(amount >= coin) {
            result.push_back(coin);
            amount -= coin;
        }
    }
    return result;
}
// 示例：找68元 → 50+10+5+1+1+1（但实际最优是20*3+5+1*3）
// ❗注意：如果币值不标准（如包含7元），贪心可能失效！

---

🆚 贪心 vs 动态规划

	贪心算法	动态规划
决策依据	当前局部最优	所有子问题最优解
计算复杂度	通常O(nlogn)	通常O(n^2)或更高
存储空间	通常O(1)	需要存储状态表
适用问题	满足贪心选择性质的问题	有重叠子问题的问题

---

❗ 贪心算法注意事项

1. 必须验证正确性（如数学归纳法证明）
2. 警惕反例：比如硬币[25,20,5,1]，找30元时贪心选25+5×1（共6枚），实际最优是20+10（但10不存在，所以贪心失败）
3. 排序预处理：很多贪心问题需要先排序
4. 结合其他算法：有时贪心作为其他算法的优化步骤

---

💡 贪心算法应用场景

1. 最小生成树：Prim算法、Kruskal算法
2. 最短路径：Dijkstra算法
3. 数据压缩：哈夫曼编码
4. 任务调度：CPU任务分配

---

🧩 练习题

1. 区间覆盖：用最少数量的点覆盖所有区间
   • 输入：[[1,3], [2,5], [4,7]]
   • 输出：2（选择3和7）
2. 跳跃游戏：数组每个元素代表最大跳跃长度，能否到终点？
   • 输入：[2,3,1,1,4]
   • 输出：true
3. 买卖股票最佳时机Ⅱ：每天可买卖多次，求最大利润
   • 策略：涨就买，跌不动