【CS.AL】算法核心之贪心算法：从入门到进阶

1000.1.CS.AL.1.4-核心-GreedyAlgorithm-Created: 2024-06-13.Thursday17:47

1. 概述

贪心算法是一种求解优化问题的算法策略。在每一步选择中，贪心算法都会选择当前最优解，希望通过一系列局部最优解的选择，达到全局最优解。贪心算法不回溯，不进行全局考虑，而是根据局部情况作出当前最优的选择。

2. 适用场景

贪心算法适用于一类特殊问题，即具有贪心选择性质的问题。这类问题满足每一步的选择都是局部最优的，并且不同步骤之间没有依赖关系，可以独立地做出选择。在这种情况下，贪心算法通常可以找到全局最优解或者近似最优解。

3. 设计步骤

1. 确定问题的最优解性质：贪心算法求解问题时，首先要确定问题是否具有最优子结构和贪心选择性质。如果满足这两个性质，那么贪心算法可能是可行的。
2. 选择合适的贪心策略：在每一步中，需要选择一个局部最优解。这就要根据问题的具体特点，设计适合的贪心策略，使得每次选择都是当前的最优解。
3. 构建贪心算法：根据选择的贪心策略，逐步构建出贪心算法，不断做出当前最优的选择，直至达到全局最优解或者满足问题的要求。

4. 优缺点

• 优点：贪心算法通常简单、高效，且易于实现。在一些特定问题中，贪心算法可以快速找到最优或近似最优解。
• 缺点：贪心算法并不适用于所有问题，有些问题并不具备贪心选择性质，因此贪心算法可能得到局部最优解而不是全局最优解。在这种情况下，需要考虑其他算法策略。

5. 典型应用

• 最小生成树问题：如Prim算法和Kruskal算法用于求解图中的最小生成树。
• 背包问题：如分数背包问题、0-1背包问题等，贪心算法在某些情况下可以得到近似最优解。
• 霍夫曼编码：用于数据压缩，通过贪心选择构建最优前缀编码。
• 最短路径问题：如Dijkstra算法和A*算法用于求解图中的最短路径。

6. 题目和代码示例

6.1 简单题目：找零问题

题目描述：给定不同面值的硬币，求最少硬币数使得总金额为给定值。

代码示例：

#include <iostream>
#include <vector>
#include <algorithm>

// 函数声明
int coinChange(std::vector<int>& coins, int amount);

int main() {
    std::vector<int> coins = {1, 2, 5};
    int amount = 11;
    std::cout << "最少硬币数: " << coinChange(coins, amount) << std::endl;
    return 0;
}

// 找零问题：求最少硬币数
int coinChange(std::vector<int>& coins, int amount) {
    // 步骤 1: 对硬币面值从大到小排序
    std::sort(coins.rbegin(), coins.rend());
    int count = 0;

    // 步骤 2: 遍历硬币面值，逐步减少目标金额
    for (int coin : coins) {
        while (amount >= coin) {
            amount -= coin;
            count++;
        }
    }

    // 步骤 3: 检查是否正好找零成功
    return amount == 0 ? count : -1;
}

Ref. ![[1000.03.CS.PL.C++.4.2-STL-Algorithms-SortingOperations#1.1 简述]]

Others.

def coin_change(coins, amount):
    coins.sort(reverse=True)
    count = 0
    for coin in coins:
        while amount >= coin:
            amount -= coin
            count += 1
    return count if amount == 0 else -1

# 示例
coins = [1, 2, 5]
amount = 11
print(coin_change(coins, amount))  # 输出: 3 (5 + 5 + 1)

6.2 中等题目：区间调度问题

题目描述：给定多个会议的开始和结束时间，求最多能安排的会议数量。

代码示例：

#include <iostream>
#include <vector>
#include <algorithm>

// 会议结构体
struct Meeting {
    int start;
    int end;
};

// 函数声明
int maxMeetings(std::vector<Meeting>& meetings);

int main() {
    std::vector<Meeting> meetings = {{1, 2}, {3, 4}, {0, 6}, {5, 7}, {8, 9}, {5, 9}};
    std::cout << "最多能安排的会议数量: " << maxMeetings(meetings) << std::endl;
    return 0;
}

// 区间调度问题：求最多能安排的会议数量
int maxMeetings(std::vector<Meeting>& meetings) {
    // 步骤 1: 根据会议结束时间排序
    std::sort(meetings.begin(), meetings.end(), [](const Meeting& a, const Meeting& b) {
        return a.end < b.end;
    });
    int count = 0;
    int endTime = 0;

    // 步骤 2: 遍历会议，选择结束时间最早的会议
    for (const auto& meeting : meetings) {
        if (meeting.start >= endTime) {
            count++;
            endTime = meeting.end;
        }
    }

    return count;
}

ref.

def max_meetings(meetings):
    meetings.sort(key=lambda x: x[1])
    count = 0
    end_time = 0
    for meeting in meetings:
        if meeting[0] >= end_time:
            count += 1
            end_time = meeting[1]
    return count

# 示例
meetings = [(1, 2), (3, 4), (0, 6), (5, 7), (8, 9), (5, 9)]
print(max_meetings(meetings))  # 输出: 4

6.3 困难题目：分数背包问题

题目描述：给定物品的重量和价值，求在背包容量限制下的最大价值，物品可以分割。

代码示例：

#include <iostream>
#include <vector>
#include <algorithm>

// 物品结构体
struct Item {
    double value;
    double weight;
};

// 函数声明
double fractionalKnapsack(std::vector<Item>& items, double capacity);

int main() {
    std::vector<Item> items = {{60, 10}, {100, 20}, {120, 30}};
    double capacity = 50;
    std::cout << "背包的最大价值: " << fractionalKnapsack(items, capacity) << std::endl;
    return 0;
}

// 分数背包问题：求在背包容量限制下的最大价值
double fractionalKnapsack(std::vector<Item>& items, double capacity) {
    // 步骤 1: 根据物品单位重量价值排序
    std::sort(items.begin(), items.end(), [](const Item& a, const Item& b) {
        return (a.value / a.weight) > (b.value / b.weight);
    });
    double totalValue = 0;

    // 步骤 2: 遍历物品，选择单位重量价值最高的物品
    for (const auto& item : items) {
        if (capacity >= item.weight) {
            capacity -= item.weight;
            totalValue += item.value;
        } else {
            totalValue += item.value * (capacity / item.weight);
            break;
        }
    }

    return totalValue;
}

ref.

def fractional_knapsack(values, weights, capacity):
    items = list(zip(values, weights))
    items.sort(key=lambda x: x[0] / x[1], reverse=True)
    total_value = 0
    for value, weight in items:
        if capacity >= weight:
            capacity -= weight
            total_value += value
        else:
            total_value += value * (capacity / weight)
            break
    return total_value

# 示例
values = [60, 100, 120]
weights = [10, 20, 30]
capacity = 50
print(fractional_knapsack(values, weights, capacity))  # 输出: 240.0

7. 题目和思路表格

8. 总结

贪心算法是一种简单而高效的算法策略，在解决满足贪心选择性质的问题时，能够得到较好的结果。然而，要注意贪心算法的局限性，它不适用于所有问题，有些问题需要考虑其他算法设计策略，如分治、动态规划等。因此，在实际应用中，需要根据问题的性质和要求选择合适的算法策略。通过理解和掌握上述贪心算法的例子和思路，能够有效地提升解决问题的能力。

References