c++算法学习5——贪心算法
一、贪心算法的原理
贪心算法（Greedy Algorithm）是一种在每一步选择中都采取当前最优决策的策略，通过局部最优解的累积逼近全局最优解。其核心思想是“着眼当前，忽略整体”，适用于满足最优子结构和贪心选择性质的问题。本文以阿里巴巴运宝藏问题为切入点，深入解析贪心算法的设计步骤、验证方法及经典应用。
二、贪心算法的核心思想
贪心算法需满足三个关键步骤：
- 确定最优子结构
问题可分解为多个子问题，且子问题的最优解能组合为全局最优解。例如背包问题中，子问题是“当前剩余容量下的最大价值”。 - 构建贪心选择策略
制定局部最优决策规则，常见策略包括：- 分类讨论（如区间覆盖问题）
- 最值搭配（如纪念品分组）
- 最大价值优先（如金属装载问题）
- 验证策略正确性
需通过数学方法证明贪心策略的全局最优性：- 数学归纳法：证明每一步选择保持最优解结构。
- 反证法：假设存在更优解，推导矛盾。
三、经典贪心问题
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;
}