c++算法学习5——贪心算法

一、贪心算法的原理

贪心算法（Greedy Algorithm）是一种在每一步选择中都采取当前最优决策的策略，通过局部最优解的累积逼近全局最优解。其核心思想是“着眼当前，忽略整体”，适用于满足​​最优子结构​​和​​贪心选择性质​​的问题。本文以阿里巴巴运宝藏问题为切入点，深入解析贪心算法的设计步骤、验证方法及经典应用。

二、贪心算法的核心思想

贪心算法需满足三个关键步骤：

1. ​​确定最优子结构​​
   问题可分解为多个子问题，且子问题的最优解能组合为全局最优解。例如背包问题中，子问题是“当前剩余容量下的最大价值”。
2. ​​构建贪心选择策略​​
   制定局部最优决策规则，常见策略包括：
   • ​​分类讨论​​（如区间覆盖问题）
   • ​​最值搭配​​（如纪念品分组）
   • ​​最大价值优先​​（如金属装载问题）
3. ​​验证策略正确性​​
   需通过数学方法证明贪心策略的全局最优性：
   • ​​数学归纳法​​：证明每一步选择保持最优解结构。
   • 反证法：假设存在更优解，推导矛盾。

三、经典贪心问题

1.题目：最大价值装载（金属分割问题）

        阿里巴巴此时已经到了强盗们藏宝的宝库，里面有许多珍贵的贵金属，但是他只带着一个口袋，口袋至多只能装重量为w的物品。宝库内的贵金属有s个种类, 每种金属重量不同，分别为n1,n2,...,ns，同时每个种类的金属总的价值也不同，分别为v1,v2,...,vs。阿里巴巴想一次带走价值尽可能多的金属，问他最多能带走价值多少的金属。注意：金属是可以被任意分割的，并且金属的价值和其重量成正比。   

【输入】 第1行是测试数据的组数k，后面跟着k组输入。 每组测试数据占3行，第1行是一个正整数w(1≤w≤10000)，表示口袋承重上限。第2行是一个正整数s(1≤s≤100)，表示金属种类。第3行有2s个正整数，分别为n1,v1,n2,v2,...,ns,vs分别为第一种，第二种，...，第s种金属的总重量和总价值(1≤ni≤10000,1≤vi≤10000)。

【输出】 k行，每行输出对应一个输入。输出应精确到小数点后2位。

【输入样例】

 2           

 50          

 4          

10 100 50 30 7 34 87 100  

10000  

5  

1 43 43 323 35 45 43 54 87 43

【输出样例】

 171.93                

 508.00    

2.题目分析：

2.1问题描述：

给定口袋的承重上限w和s种金属，每种金属的总重量和总价值已知，金属可以分割并且价值与重量成正比。目标是尽可能多地带走最大总价值的金属。

2.2确定问题的最优子结构：        

每个子结构都旨在实现，当前背包承重下可获得的最大价值的金属重量。

如何实现：

      存储：要考虑重量、价值以及单位价值三者，可以用结构体进行存储。

                 struct Metal{  // 定义结构体Metal    

                  int weight;  // 总重量    

                  int value;  // 总价值    

                  double unitValue;  // 单位价值

                  };

       排序：优先选择当前单位重量价值最高的金属，  需要单独编写排序规则，  对所有金属按单位重量的价值从大到小排序。

             bool cmp(Metal m1, Metal m2){//定义比较函数cmp    

                     return m1.unitValue > m2.unitValue;

             }

2.3制定贪心策略：

在口袋能够容纳金属的情况下，优先选择当前单位重量价值最高的金属装入口袋。如果当前金属无法完全装入口袋，按照所占比例装入口袋，并计算总价值。

   if(a[j].weight <= remain){  // 如果当前金属的重量小于等于剩余容量，则将该金属全部放入背包              maxValue += a[j].unitValue * a[j].weight;          

          remain -= a[j].weight;  

  } else {  // 如果当前金属的重量大于剩余容量，则将当前金属按比例放入背包        

          maxValue += remain * a[j].unitValue;          

          remain = 0;            

          break;

}

2.4完整代码实现：

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

struct Metal {
    int weight;  // 总重量 n_i
    int value;   // 总价值 v_i
    double unitValue; // 单位价值
};

bool cmp(Metal m1, Metal m2) {
    return m1.unitValue > m2.unitValue; // 按单位价值降序排序
}

int main() {
    int k;
    cin >> k; // 测试数据组数
    while (k--) {
        int W, S;
        cin >> W >> S; // 承重W, 金属种类S
        Metal a[105];
        for (int i = 0; i < S; i++) {
            cin >> a[i].weight >> a[i].value;
            a[i].unitValue = static_cast<double>(a[i].value) / a[i].weight;
        }
        sort(a, a + S, cmp); // 关键：按单位价值排序

        double maxValue = 0;
        int remain = W; // 剩余承重
        for (int i = 0; i < S; i++) {
            if (a[i].weight <= remain) { // 完整装载当前金属
                maxValue += a[i].value;
                remain -= a[i].weight;
            } else { // 部分装载
                maxValue += remain * a[i].unitValue;
                remain = 0;
                break;
            }
        }
        printf("%.2lf\n", maxValue); // 输出最大价值
    }
    return 0;
}