贪心算法

算法定义

贪心算法（Greedy Algorithm）是一种在每一步选择中都采取当前状态下最优（即最有利）的选择，从而希望导致结果是全局最优的解题策略。它不考虑整体最优，仅关注局部最优选择，通过一系列局部最优决策来构建全局解。

算法思路

  1. 建立数学模型描述问题
  2. 把求解的问题分成若干个子问题
  3. 对每个子问题求解，得到子问题的局部最优解
  4. 将子问题的局部最优解合成原来问题的一个解

算法复杂度

  • 时间复杂度：
    • 最好情况：O (n)，如某些线性扫描即可找到最优解的问题
    • 最坏情况：O (n²) 或 O (n log n)，取决于具体问题和排序等预处理操作
    • 平均情况：通常介于最好和最坏情况之间
  • 空间复杂度：
    • 通常为 O (n)，主要用于存储问题数据和中间结果

优点和缺点

  • 优点：
    • 算法简单直观，易于实现
    • 时间和空间复杂度较低，执行效率高
    • 对于具有贪心选择性质的问题，能得到最优解
  • 缺点：
    • 不能保证得到全局最优解，只能得到局部最优解
    • 不适用于所有问题，仅适用于具有贪心选择性质和最优子结构的问题
    • 选择的贪心策略对结果影响很大

应用场景

  • 哈夫曼编码（数据压缩）
  • 最小生成树（Prim 算法、Kruskal 算法）
  • 最短路径（Dijkstra 算法）
  • 活动选择问题
  • 背包问题（部分背包问题）
  • 区间调度问题
  • 找零钱问题

Java 代码实现

import java.util.*;

public class GreedyAlgorithm {
    
    // 1. 基础实现：找零钱问题
    public static Map<Integer, Integer> makeChangeBasic(int amount, int[] denominations) {
        Map<Integer, Integer> result = new HashMap<>();
        // 按面额从大到小排序
        Arrays.sort(denominations);
        reverse(denominations);
        
        for (int coin : denominations) {
            if (amount >= coin) {
                int count = amount / coin;
                result.put(coin, count);
                amount -= count * coin;
            }
            if (amount == 0) {
                break;
            }
        }
        
        if (amount > 0) {
            throw new IllegalArgumentException("无法用给定面额凑出目标金额");
        }
        
        return result;
    }
    
    // 2. 优化实现：使用List保存结果，更高效
    public static List<int[]> makeChangeOptimized(int amount, int[] denominations) {
        List<int[]> result = new ArrayList<>();
        Arrays.sort(denominations);
        reverse(denominations);
        
        for (int coin : denominations) {
            if (amount >= coin) {
                int count = amount / coin;
                result.add(new int[]{coin, count});
                amount -= count * coin;
            }
            if (amount == 0) {
                break;
            }
        }
        
        if (amount > 0) {
            throw new IllegalArgumentException("无法用给定面额凑出目标金额");
        }
        
        return result;
    }
    
    // 3. 处理无法整除的情况：返回最接近的组合
    public static List<int[]> makeChangeWithFallback(int amount, int[] denominations) {
        List<int[]> result = new ArrayList<>();
        Arrays.sort(denominations);
        reverse(denominations);
        
        int originalAmount = amount;
        
        for (int coin : denominations) {
            if (amount >= coin) {
                int count = amount / coin;
                result.add(new int[]{coin, count});
                amount -= count * coin;
            }
            if (amount == 0) {
                break;
            }
        }
        
        // 如果无法完全凑出，返回最接近的组合
        if (amount > 0) {
            System.out.println("警告：无法完全凑出 " + originalAmount + "，只能凑出 " + (originalAmount - amount));
        }
        
        return result;
    }
    
    // 辅助方法：反转数组
    private static void reverse(int[] array) {
        for (int i = 0; i < array.length / 2; i++) {
            int temp = array[i];
            array[i] = array[array.length - 1 - i];
            array[array.length - 1 - i] = temp;
        }
    }
    
    // 测试
    public static void main(String[] args) {
        int[] denominations = {1, 5, 10, 20, 50, 100};
        int amount = 376;
        
        // 测试基础实现
        System.out.println("基础实现:");
        Map<Integer, Integer> basicResult = makeChangeBasic(amount, denominations.clone());
        for (Map.Entry<Integer, Integer> entry : basicResult.entrySet()) {
            System.out.println(entry.getKey() + "元: " + entry.getValue() + "张");
        }
        
        // 测试优化实现
        System.out.println("\n优化实现:");
        List<int[]> optimizedResult = makeChangeOptimized(amount, denominations.clone());
        for (int[] pair : optimizedResult) {
            System.out.println(pair[0] + "元: " + pair[1] + "张");
        }
        
        // 测试带容错的实现
        System.out.println("\n带容错的实现:");
        int[] specialDenominations = {3, 5, 7};
        List<int[]> fallbackResult = makeChangeWithFallback(8, specialDenominations.clone());
        for (int[] pair : fallbackResult) {
            System.out.println(pair[0] + "元: " + pair[1] + "张");
        }
    }
}

代码解析

上面的代码实现了三种不同的贪心算法写法：

  1. 基础实现：使用 HashMap 存储每种面额的数量，直观易懂，但 HashMap 的开销稍大
  2. 优化实现：使用 List 存储结果，每个元素是一个包含面额和数量的数组，减少了 HashMap 的额外开销，效率更高
  3. 带容错的实现：当无法用给定面额完全凑出目标金额时，返回最接近的组合，而不是抛出异常，增加了算法的鲁棒性

这些实现都遵循贪心算法的核心思想：在每一步选择当前最优（即最大面额的硬币），逐步构建问题的解。

需要注意的是，贪心算法并不适用于所有问题。例如，对于某些硬币面额组合（如 {1, 3, 4}），贪心算法可能无法得到最优解。在这种情况下，可能需要使用动态规划等其他算法。

最近更新：:
Contributors: luokaiwen