「Java实战」贪心算法VS穷举法：从理论解析到案例实战，全面掌握算法精髓
·
目录
引言
贪心算法和穷举法是两种常用的算法策略，它们在解决实际问题时各有优劣。本文将通过具体的案例来探讨这两种算法的应用，并提供Java实现的代码示例。我们将使用Java 1.8版本，并使用IntelliJ IDEA 2024.1.4作为开发工具。
项目概述
本项目通过Java语言实现了贪心算法和穷举法的具体应用案例：广播覆盖问题和钱币找零问题。通过这些案例，读者可以更好地理解这两种算法的工作原理及其适用场景。
技术栈
- Java 1.8：用于编写程序逻辑。
- JUnit 5：用于编写单元测试。
- HashMap 和 HashSet：用于存储数据结构。
- 递归：用于穷举法中的深度优先搜索。
- 控制流语句：如
for循环、while循环等，用以控制程序执行流程。
贪心算法详解
贪心算法是一种在每一步选择中都采取当前状态下最好或最优（即最有利）的选择，从而希望导致结果是全局最好或最优的算法策略。贪心算法特别适用于那些具有最优子结构性质的问题，即局部最优解能决定全局最优解的问题。
特点
- 贪心选择性质：问题的整体最优解可以通过一系列局部的最优解达到，并且每次的选择可以依赖以前作出的选择，但不依赖于后面要作出的选择。
- 最优子结构性质：问题的最优解包含其子问题的最优解时，称此问题具有最优子结构性质。
局限性
贪心算法并不保证得到全局最优解，有时产生的全局解可能不是最优的。因此，在使用贪心算法时需要评估其适用性和局限性。
穷举法详解
穷举法是一种解决问题的方法，通过遍历所有可能的情况，找到满足条件的结果。虽然穷举法能够保证找到最优解，但其效率往往较低，特别是在问题规模较大时。
特点
- 全面性：能够找到所有可能的解。
- 低效性：当问题规模较大时，计算量呈指数级增长。
广播覆盖问题
问题描述
已知有5个广播电台，每个电台都有自己的覆盖地区。需要选择最少的广播台，让所有的地区都可以接收到信号。
贪心算法解决方案
通过选择每次覆盖最多未覆盖地区的电台，逐步减少未覆盖的地区，直到所有地区都被覆盖。
穷举法解决方案
通过遍历所有可能的电台组合，找到能够覆盖所有地区的最小电台集合。
钱币找零问题
问题描述
给定不同面额的钱币，如何找零使得使用的钱币数量最少。
贪心算法解决方案
从大到小依次选择硬币，直到凑够所需金额或无法继续找零。
穷举法解决方案
通过递归尝试所有可能的找零组合，找到最少的硬币数。
代码示例
以下是完整的Java代码和完整注释，包含了上述提到的所有算法的实现：
package com.chenze.design.practice.greedyandexhaustive;
import org.junit.Test;
import java.util.*;
import java.util.concurrent.atomic.AtomicInteger;
/**
* 贪心算法和穷举法理解和案例
*/
public class GreedyAndExhaustiveAlgorithm {
/**
* 1.贪心算法：
* 贪心算法是一种在每一步选择中都采取在当前状态下最好或最优（即最有利）的选择，从而希望导致结果是全局最好或最优的算法策略。
* 贪心算法特别适用于那些具有最优子结构性质的问题，即局部最优解能决定全局最优解的问题。
* 贪心算法的核心思想是在每一步选择中都做出在当前看来是最好的选择，而不考虑各种可能的整体情况。
* 这种方法省去了为找最优解要穷尽所有可能而必须耗费的大量时间。
* 贪心算法采用自顶向下的方法，通过迭代的方式逐步简化问题规模，每一步的选择都基于当前的状态和优化测度，最终得到一个局部最优解。
* 然而，贪心算法并不保证得到全局最优解，有时产生的全局解可能不是最优的。
* 贪心算法的适用场景通常具有以下特征：
* 贪心选择性质：问题的整体最优解可以通过一系列局部的最优解达到，并且每次的选择可以依赖以前作出的选择，但不依赖于后面要作出的选择。
* 最优子结构性质：问题的最优解包含其子问题的最优解时，称此问题具有最优子结构性质。这是贪心算法求解的关键所在。
* 贪心算法的经典例子包括：
* 活动选择问题：在多个活动中选择一些活动参加，每个活动有一个结束时间，选择结束时间最早的活动可以使得选择的活动的数量最多。
* 钱币找零问题：给定不同面额的钱币，如何找零使得使用的钱币数量最少。
* 背包问题：在限定重量的背包中装入物品，使得物品的总价值最大。
* 小船过河问题：小船过河需要支付费用，如何安排过河顺序使得总费用最小。
* 区间覆盖问题：给定一系列区间，选择最少的区间覆盖所有的点。
* 贪心算法的局限在于它不保证得到全局最优解，有时产生的解可能不是最优的。因此，在使用贪心算法时需要评估其适用性和局限性。
* 总结：
* 1、每一次都选择当前最优解
* 2、《向前看，别回头》
* 2.穷举法：穷举法是一种解决问题的方法，通过遍历所有可能的情况，找到满足条件的结果。
* 以下我就运用贪心算法和穷举思想解决：广播覆盖问题和钱币找零问题
*/
/**
* 广播覆盖问题：
* 已知有5个广播电台，每个电台都有自己的覆盖地区，其中分别是
* 第一个广播电台为"K1",覆盖地区为"北京", "上海", "天津"
* 第二个广播电台为"K2",覆盖地区为"广州", "北京", "深圳"
* 第三个广播电台为"K3",覆盖地区为"成都", "上海", "杭州"
* 第四个广播电台为"K4",覆盖地区为"上海", "天津"
* 第五个广播电台为"K5",覆盖地区为"杭州", "大连"
* 需要覆盖地区为：北京，上海，天津，广州，深圳，成都，杭州，大连
* 如何选择最少的广播台，让所有的地区都可以接收到信号？
* 1、运用穷举法，就需要进行遍历所有的可能性，但是，若广播的数量和覆盖的地区需要很多时，那么效率就会非常的差，但是穷举法能解决问题。
* 2、运用贪心算法，可以高效的解决问题，但是不一定是最优解，有些时候不能解决所有的问题。
* 下面的代码，实现了使用贪心算法和穷举法解决广播电台覆盖问题，
*/
/**
* 贪心算法解决广播电台覆盖问题
*/
@Test
public void broadcastSelection() {
// 创建广播电台, 放入到Map
HashMap<String, HashSet<String>> broadcasts = createBroadcasts();
// allAreas 存放所有的地区
HashSet<String> allAreas = createAllAreas();
// 创建ArrayList, 存放选择的电台集合
ArrayList<String> selects = new ArrayList<>();
// 定义一个临时的集合， 在遍历的过程中，存放遍历过程中的电台覆盖的地区和当前还没有覆盖的地区的交集
HashSet<String> tempSet = new HashSet<>();
String maxKey = null;
// 当还有未覆盖的地区时，继续选择电台
while (!allAreas.isEmpty()) {
maxKey = null;
int maxSize = 0;
// 遍历所有电台，寻找能覆盖最多未覆盖地区的电台
for (String key : broadcasts.keySet()) {
tempSet.clear();
HashSet<String> strings = broadcasts.get(key);
tempSet.addAll(strings);
tempSet.retainAll(allAreas);
// 如果当前电台覆盖的未覆盖地区数量大于当前最大值，则更新最大值和对应的电台
if (!tempSet.isEmpty() && tempSet.size() > maxSize) {
maxKey = key;
maxSize = tempSet.size();
}
}
// 如果找到了能覆盖未覆盖地区的电台，则将其添加到选择集合中，并从未覆盖地区中移除已覆盖的地区
if (maxKey != null) {
allAreas.removeAll(broadcasts.get(maxKey));
selects.add(maxKey);
}
}
// 输出最终选择的电台集合
System.out.println("得到的选择结果是" + selects); // [K1,K2,K3,K5]
}
/**
* 创建广播电台和其覆盖地区的映射
* @return 包含广播电台和其覆盖地区的HashMap
*/
private static HashMap<String, HashSet<String>> createBroadcasts() {
HashMap<String, HashSet<String>> broadcasts = new HashMap<>();
// 创建各个广播电台覆盖的地区集合
HashSet<String> hashSet1 = new HashSet<>();
hashSet1.add("北京");
hashSet1.add("上海");
hashSet1.add("天津");
HashSet<String> hashSet2 = new HashSet<>();
hashSet2.add("广州");
hashSet2.add("北京");
hashSet2.add("深圳");
HashSet<String> hashSet3 = new HashSet<>();
hashSet3.add("成都");
hashSet3.add("上海");
hashSet3.add("杭州");
HashSet<String> hashSet4 = new HashSet<>();
hashSet4.add("上海");
hashSet4.add("天津");
HashSet<String> hashSet5 = new HashSet<>();
hashSet5.add("杭州");
hashSet5.add("大连");
// 将广播电台和其覆盖的地区加入到map中
broadcasts.put("K1", hashSet1);
broadcasts.put("K2", hashSet2);
broadcasts.put("K3", hashSet3);
broadcasts.put("K4", hashSet4);
broadcasts.put("K5", hashSet5);
return broadcasts;
}
/**
* 创建需要覆盖的所有地区集合
* @return 包含所有需要覆盖地区的HashSet
*/
private static HashSet<String> createAllAreas() {
HashSet<String> allAreas = new HashSet<>();
// 添加所有需要覆盖的地区
allAreas.add("北京");
allAreas.add("上海");
allAreas.add("天津");
allAreas.add("广州");
allAreas.add("深圳");
allAreas.add("成都");
allAreas.add("杭州");
allAreas.add("大连");
return allAreas;
}
/**
* 穷举法解决广播电台覆盖问题
*/
@Test
public void broadcastSelection1() {
// 创建广播电台, 放入到Map
HashMap<String, HashSet<String>> broadcasts = createBroadcasts();
// allAreas 存放所有的地区
HashSet<String> allAreas = createAllAreas();
// 获取所有电台的名称
List<String> broadcastKeys = new ArrayList<>(broadcasts.keySet());
int n = broadcastKeys.size();
// 初始化最小电台数量为最大值
int minStationsCount = Integer.MAX_VALUE;
ArrayList<String> bestStations = new ArrayList<>();
// 穷举所有可能的电台组合
for (int i = 1; i < (1 << n); i++) {
HashSet<String> coveredAreas = new HashSet<>();
ArrayList<String> selectedStations = new ArrayList<>();
// 检查每个电台是否在当前组合中
for (int j = 0; j < n; j++) {
if ((i & (1 << j)) != 0) {
selectedStations.add(broadcastKeys.get(j));
coveredAreas.addAll(broadcasts.get(broadcastKeys.get(j)));
}
}
// 如果当前组合覆盖了所有地区且电台数量更少，则更新最佳组合
if (coveredAreas.containsAll(allAreas) && selectedStations.size() < minStationsCount) {
minStationsCount = selectedStations.size();
bestStations = selectedStations;
}
}
// 输出最终选择的电台组合
System.out.println("得到的选择结果是" + bestStations);
}
/**
* 钱币找零问题:
* 若有18元，需要进行找零钱，已知零钱为[5,2,1]这三个零钱
* 请问最少需要找多少个硬币？
* 1.运用穷举法，可以有效的解决问题，但是效率会差很多。
* 2.运用贪心算法，那么有些情况不能解决，
* 比如：[1,15,10]， 21，
* 运用贪心算法思想，就是一个15，六个1，共七个硬币
* 但是实际上最少的应该是两个10，一个1，共3个硬币（穷举法可以进行解决）
* 那么贪心算法无法解决，但是穷举法可以解决。
* 下面的代码，实现了使用贪心算法和穷举法解决钱币找零问题
*/
/**
* 运用贪心算法解决钱币找零问题
*/
@Test
public void currencyChange() {
// 调用coinChange方法计算最少需要的硬币数量
int count = coinChange(new int[]{5, 2, 1}, 18);
// 输出计算结果
System.out.println("count = " + count);
}
/**
* 使用贪心算法解决硬币找零问题
* @param coins 可用的硬币面额数组
* @param amount 需要找零的总金额
* @return 返回找零所需的最少硬币数量，如果无法凑出则返回-1
*/
public int coinChange(int[] coins, int amount) {
// 初始化剩余金额为需要找零的总金额
int remainder = amount;
// 初始化硬币计数器
int count = 0;
// 遍历硬币面额数组，从大到小尝试使用硬币
for (int coin : coins) {
// 当剩余金额大于当前硬币面额时，使用该硬币进行找零
while (remainder > coin) {
// 减去当前硬币面额
remainder -= coin;
// 硬币计数器增加
count++;
}
// 当剩余金额等于当前硬币面额时，使用该硬币完成找零
if (remainder == coin) {
// 剩余金额归零
remainder = 0;
// 硬币计数器增加
count++;
// 找零完成，跳出循环
break;
}
}
// 检查最终剩余金额是否为零
if (remainder > 0) {
// 如果剩余金额不为零，表示无法凑出，返回-1
return -1;
} else {
// 如果剩余金额为零，返回使用的硬币数量
return count;
}
}
/**
* 运用穷举法解决钱币找零问题
*/
@Test
public void currencyChange1(){
// 调用coinChange1函数计算找零的最少硬币数
int count = coinChange1(new int[]{5, 2, 1}, 18);
// 输出最少硬币数
System.out.println("count = " + count);
}
// 初始化需要的最少硬币数为-1，表示未找到解
static int min = -1;
/**
* 解决钱币找零问题的函数
* @param coins 可用的硬币面额数组
* @param amount 需要找零的金额
* @return 返回找零的最少硬币数，如果无法找零则返回-1
*/
public int coinChange1(int[] coins, int amount) {
// 使用栈来记录当前的找零组合
LinkedList<Integer> stack = new LinkedList<>();
// 遍历每一种硬币面额，尝试作为找零的起始硬币
for (int i = 0; i < coins.length; i++) {
// 调用递归函数开始尝试找零
rec(i, coins, amount - coins[i], new AtomicInteger(0), stack);
}
// 返回最少硬币数
return min;
}
/**
* 递归函数，用于尝试所有可能的找零组合
* @param index 当前考虑的硬币索引
* @param coins 可用的硬币面额数组
* @param remainder 剩余需要找零的金额
* @param count 当前已使用的硬币数计数器
* @param stack 用于记录当前的找零组合
*/
public void rec(int index, int[] coins, int remainder, AtomicInteger count, LinkedList<Integer> stack) {
// 将当前考虑的硬币加入到栈中
stack.push(coins[index]);
// 计数器加一
count.incrementAndGet();
// 如果剩余需要找零的金额为0，说明找到了一种找零组合
if (remainder == 0) {
// 输出当前的找零组合
System.out.println(stack);
// 更新最少硬币数
if (min == -1) {
min = count.get();
} else {
min = Integer.min(min, count.get());
}
} else if (remainder > 0) {
// 如果剩余需要找零的金额大于0，继续尝试使用当前及之后的硬币面额进行找零
for (int i = index; i < coins.length; i++) {
rec(i, coins, remainder - coins[i], count, stack);
}
}
// 回溯，计数器减一，移除栈顶元素，准备尝试下一种组合
count.decrementAndGet();
stack.pop();
}
}
Maven依赖配置
为了运行上述代码中的JUnit测试，你需要在项目的pom.xml文件中添加以下Maven依赖配置：
<project xmlns="http://maven.apache.org/POM/4.0.0"
xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"
xsi:schemaLocation="http://maven.apache.org/POM/4.0.0 http://maven.apache.org/xsd/maven-4.0.0.xsd">
<modelVersion>4.0.0</modelVersion>
<groupId>com.example</groupId>
<artifactId>greedy-and-exhaustive-algorithm</artifactId>
<version>1.0-SNAPSHOT</version>
<properties>
<maven.compiler.source>1.8</maven.compiler.source>
<maven.compiler.target>1.8</maven.compiler.target>
</properties>
<dependencies>
<!-- JUnit 5 dependency -->
<dependency>
<groupId>org.junit.jupiter</groupId>
<artifactId>junit-jupiter-engine</artifactId>
<version>5.8.1</version>
<scope>test</scope>
</dependency>
</dependencies>
<build>
<plugins>
<plugin>
<groupId>org.apache.maven.plugins</groupId>
<artifactId>maven-surefire-plugin</artifactId>
<version>3.0.0-M5</version>
</plugin>
</plugins>
</build>
</project>
确保你的pom.xml文件中包含上述依赖配置。这样，你可以使用Maven来编译和运行测试。
运行结果截图
-
贪心算法解决广播电台覆盖问题
-
穷举法解决广播电台覆盖问题
-
运用贪心算法解决钱币找零问题
-
运用穷举法解决钱币找零问题
结论
通过上述代码示例，我们可以看到如何使用Java 1.8实现贪心算法和穷举法来解决广播覆盖问题和钱币找零问题。贪心算法虽然高效，但不一定能得到全局最优解；而穷举法则能保证找到最优解，但效率较低。了解这两种算法的特点和适用场景有助于我们在实际开发中做出合适的选择。
参考资料
- Oracle官方文档：Java SE Documentation
- CSDN博客：Java基础知识教程
- 维基百科：Greedy Algorithm
- 维基百科：Exhaustive Search
这篇文章旨在为初学者提供一份详细的贪心算法和穷举法实践指南，希望这篇指南对你有所帮助，同时鼓励大家不断探索和创新。如果你有任何问题或建议，请随时留言交流！
更多推荐
36
0- 0
已为社区贡献1条内容
所有评论(0)