贪心算法特性和解题步骤、分数背包问题篇
贪心算法特性和解题步骤、分数背包问题篇
贪心算法是一种常见的优化问题解决方案，以其简洁高效的特点在各种场景中广泛应用。本文将详细介绍贪心算法的基本概念、特性、解题步骤，并通过分数背包问题进行具体应用的讲解。
1、贪心算法
贪心算法的基本思想是在问题的每个决策阶段，都选择当前看起来最优的选择，即贪心地做出局部最优决策，以期获得全局最优解。与动态规划相似，贪心算法也常用于解决优化问题，但其工作原理有所不同：
- 动态规划：根据之前阶段所有决策来考虑当前决策，并使用过去子问题解来构建当前子问题解。
- 贪心算法：不会考虑过去决策，而是一路向前地进行贪心选择，不断缩小问题范围，直至问题被解决。
例如，给定n种硬币，第i种硬币的面值为coins[i-1]，目标金额为amt，每种硬币可以重复选取，目标是凑出目标金额的最少硬币数量。如果无法凑出目标金额，则返回-1。贪心算法的实现如下：
/* 零钱兑换：贪心 */
int coinChangeGreedy(int[] coins, int amt) {
// 假设 coins 列表有序
int i = coins.length - 1;
int count = 0;
// 循环进行贪心选择，直到无剩余金额
while (amt > 0) {
// 找到小于且最接近剩余金额的硬币
while (i > 0 && coins[i] > amt) {
i--;
}
// 选择 coins[i]
amt -= coins[i];
count++;
}
// 若未找到可行方案，则返回 -1
return amt == 0 ? count : -1;
}
1.1、贪心算法优点与局限性
贪心算法的优点是操作直接、实现简单，而且通常效率也很高。然而，对于某些硬币面值组合，贪心算法并不能找到最优解。对于零钱兑换问题，贪心算法无法保证找到全局最优解，并且有可能找到非常差的解。更适合用动态规划解决。
贪心算法适用情况分两种：
- 保证找到最优解：往往是最优选择，往往比回溯、动态规划更高效。
- 找到近似最优解：对于很多复杂问题来说，寻找全局最优解非常困难，能以较高效率找到次优解也是非常不错。
1.2、贪心算法特性
相较于动态规划，贪心算法使用条件更加苛刻，其主要关注问题的两个性质：
- 贪心选择性质：只有当局部最优选择始终导致全局最优解时，贪心算法才能保证得到最优解。
- 最优子结构：原问题的最优解包含子问题的最优解。
1.3、贪心算法解题步骤
解决流程分为三步：
- 问题分析：梳理与理解问题特性，包括状态定义、优化目标和约束条件等。
- 确定贪心策略：确定如何在每一步中做出贪心选择。策略能够在每一步减小问题规模，并最终解决整个问题。
- 正确性证明：通常需要证明问题具有贪心选择性质和最优子结构。步骤可能需要用到数学证明，例如归纳法或反证法等。
确定贪心策略是求解问题的核心步骤，但实施起来可能并不容易，主要有以下原因：
- 不同问题的贪心策略差异较大。对于许多问题来说，贪心策略比较浅显，通过大概思考与尝试就能得出。而对于一些复杂问题，贪心策略可能非常隐蔽，非常考验个人的解题经验与算法能力。
- 某些贪心策略具有较强的迷惑性。设计好贪心策略，写出解题代码并提交运行，很可能发现部分测试样例无法通过。设计贪心策略只是“部分正确”的，
1.4、贪心算法典型例题
贪心算法常常应用在满足贪心选择性质和最优子结构的优化问题中，典型贪心算法问题：
- 硬币找零问题：在某些硬币组合下，贪心算法总是得到最优解。
- 区间调度问题：假设一些任务，每个任务在一段时间内进行，目标是完成尽可能多的任务。每次都选择结束时间最早的任务，贪心算法得到最优解。
- 分数背包问题：给定一组物品和一个载重量，目标是选择一组物品，使得总重量不超过载重量，且总价值最大。每次都选择性价比最高（价值 / 重量）的物品，贪心算法在一些情况下得到最优解。
- 股票买卖问题：给定一组股票的历史价格，进行多次买卖，已经持有股票，在卖出之前不能再买，目标是获取最大利润。
- 霍夫曼编码：霍夫曼编码是一种用于无损数据压缩的贪心算法。通过构建霍夫曼树，每次选择出现频率最低的两个节点合并，最后得到的霍夫曼树的带权路径长度（编码长度）最小。
- Dijkstra 算法：一种解决给定源顶点到其余各顶点的最短路径问题的贪心算法。
2、分数背包问题
给定n个物品，第i个物品的重量为wgt[i-1]、价值为val[i-1]，和一个容量为cap的背包。每个物品只能选择一次，但可以选择物品的一部分，价值根据选择的重量比例计算，问在限定背包容量下背包中物品的最大价值。
对物品任意地进行切分，并按照重量比例来计算相应价值。
2.1、贪心策略确定
最大化背包内物品总价值，本质上是最大化单位重量下物品价值。贪心策略：
- 将物品按照单位价值从高到低进行排序。
- 遍历所有物品，每轮贪心地选择单位价值最高的物品。
- 若剩余背包容量不足，则使用当前物品的一部分填满背包。
2.2、代码实现
建立一个物品类 Item ，以便将物品按照单位价值进行排序。循环进行贪心选择，当背包已满时跳出并返回解。
/* 物品 */
class Item {
int w; // 物品重量
int v; // 物品价值
public Item(int w, int v) {
this.w = w;
this.v = v;
}
}
/* 分数背包：贪心 */
double fractionalKnapsack(int[] wgt, int[] val, int cap) {
// 创建物品列表，包含两个属性：重量、价值
Item[] items = new Item[wgt.length];
for (int i = 0; i < wgt.length; i++) {
items[i] = new Item(wgt[i], val[i]);
}
// 按照单位价值 item.v / item.w 从高到低进行排序
Arrays.sort(items, Comparator.comparingDouble(item -> -((double) item.v / item.w)));
// 循环贪心选择
double res = 0;
for (Item item : items) {
if (item.w <= cap) {
// 若剩余容量充足，则将当前物品整个装进背包
res += item.v;
cap -= item.w;
} else {
// 若剩余容量不足，则将当前物品的一部分装进背包
res += (double) item.v / item.w * cap;
// 已无剩余容量，因此跳出循环
break;
}
}
return res;
}
2.3、正确性证明
采用反证法。单位价值更大的物品总是更优选择，说明贪心策略有效。