JUnit 5：用于编写单元测试

引言

贪心算法和穷举法是两种常用的算法策略，它们在解决实际问题时各有优劣。运用贪心算法，可以高效的解决问题，但是不一定是最优解，有些时候不能解决所有的问题。 * 下面的代码，实现了使用贪心算法和穷举法解决钱币找零问题 *//** * 运用贪心算法解决钱币找零问题 */@TestpublicvoidcurrencyChange(){// 调用coinChange方法计算最少需要的硬币数量intcount =coinChange(newint[]{5,2,1},18);// 输出计算结果System.out.println("count = "+count);}/** * 使用贪心算法解决硬币找零问题 * @param coins 可用的硬币面额数组 * @param amount 需要找零的总金额 * @return 返回找零所需的最少硬币数量，如果无法凑出则返回-1 */publicintcoinChange(int[]coins,intamount){// 初始化剩余金额为需要找零的总金额intremainder =amount;// 初始化硬币计数器intcount =0;// 遍历硬币面额数组，从大到小尝试使用硬币for(intcoin :coins){// 当剩余金额大于当前硬币面额时，使用该硬币进行找零while(remainder >coin){// 减去当前硬币面额remainder -=coin;// 硬币计数器增加count++;}// 当剩余金额等于当前硬币面额时，使用该硬币完成找零if(remainder ==coin){// 剩余金额归零remainder =0;// 硬币计数器增加count++;// 找零完成，跳出循环break;}}// 检查最终剩余金额是否为零if(remainder >0){// 如果剩余金额不为零，表示无法凑出，返回-1return-1;}else{// 如果剩余金额为零，返回使用的硬币数量returncount;}}/** * 运用穷举法解决钱币找零问题 */@TestpublicvoidcurrencyChange1(){// 调用coinChange1函数计算找零的最少硬币数intcount =coinChange1(newint[]{5,2,1},18);// 输出最少硬币数System.out.println("count = "+count);}// 初始化需要的最少硬币数为-1，表示未找到解staticintmin =-1;/** * 解决钱币找零问题的函数 * @param coins 可用的硬币面额数组 * @param amount 需要找零的金额 * @return 返回找零的最少硬币数，如果无法找零则返回-1 */publicintcoinChange1(int[]coins,intamount){// 使用栈来记录当前的找零组合LinkedList<Integer>stack =newLinkedList<>();// 遍历每一种硬币面额，尝试作为找零的起始硬币for(inti =0;i <coins.length;i++){// 调用递归函数开始尝试找零rec(i,coins,amount -coins[i],newAtomicInteger(0),stack);}// 返回最少硬币数returnmin;}/** * 递归函数，用于尝试所有可能的找零组合 * @param index 当前考虑的硬币索引 * @param coins 可用的硬币面额数组 * @param remainder 剩余需要找零的金额 * @param count 当前已使用的硬币数计数器 * @param stack 用于记录当前的找零组合 */publicvoidrec(intindex,int[]coins,intremainder,AtomicIntegercount,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());}}elseif(remainder >0){// 如果剩余需要找零的金额大于0，继续尝试使用当前及之后的硬币面额进行找零for(inti =index;i <coins.length;i++){rec(i,coins,remainder -coins[i],count,stack);}}// 回溯，计数器减一，移除栈顶元素，准备尝试下一种组合count.decrementAndGet();stack.pop();}}

Maven依赖配置

为了运行上述代码中的JUnit测试，你需要在项目的pom.xml文件中添加以下Maven依赖配置：

<projectxmlns="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文件中包含上述依赖配置。因此，在使用贪心算法时需要评估其适用性和局限性。 * 2、

代码示例

以下是完整的Java代码和完整注释，包含了上述提到的所有算法的实现：

packagecom.chenze.design.practice.greedyandexhaustive;importorg.junit.Test;importjava.util.*;importjava.util.concurrent.atomic.AtomicInteger;/** * 贪心算法和穷举法理解和案例 */publicclassGreedyAndExhaustiveAlgorithm{/**     * 1.贪心算法：     * ‌贪心算法‌是一种在每一步选择中都采取在当前状态下最好或最优（即最有利）的选择，从而希望导致结果是全局最好或最优的算法策略。
特点
贪心选择性质：问题的整体最优解可以通过一系列局部的最优解达到，并且每次的选择可以依赖以前作出的选择，但不依赖于后面要作出的选择。
局限性
贪心算法并不保证得到全局最优解，有时产生的全局解可能不是最优的。