15-贪心算法

一，定义

贪心算法的核心思想

贪心算法的特点是：

1. 局部最优：在每一步选择中，都选择当前看起来最好的选项。

2. 不可回退：一旦做出选择，就不再回头重新考虑。

3. 希望全局最优：通过一系列局部最优的选择，最终达到全局最优。

贪心算法并不一定能得到全局最优解，但在某些问题中，它可以高效地找到一个接近最优的解。

---

举个例子

假设你有以下硬币面值：1 元、5 元、10 元，现在需要凑出 18 元，如何使用最少的硬币？

贪心算法的思路是：

1. 每次都选择面值最大的硬币。

2. 先用 10 元，剩下 8 元。

3. 再用 5 元，剩下 3 元。

4. 最后用 3 个 1 元。

5. 总共用了 5 个硬币（10 + 5 + 1 + 1 + 1）。

在这个例子中，贪心算法得到了最优解。但需要注意的是，贪心算法并不总是能得到最优解。比如，如果硬币面值是 1 元、4 元、5 元，要凑出 8 元：

• 贪心算法会选择 5 + 1 + 1 + 1，用了 4 个硬币。

• 但实际上最优解是 4 + 4，只用 2 个硬币。

---

贪心算法的适用场景

贪心算法适用于满足以下条件的问题：

1. 最优子结构：问题的最优解可以通过子问题的最优解推导出来。

2. 贪心选择性质：每一步的局部最优选择能够导致全局最优解。

常见的贪心算法应用场景包括：

• 找零钱问题（如上面的硬币例子）。

• 活动选择问题（选择最多的互不冲突的活动）。

• 最小生成树问题（如 Kruskal 算法和 Prim 算法）。

• 霍夫曼编码（用于数据压缩）。

---

贪心算法的优缺点

优点：

• 简单直观：容易理解和实现。

• 高效：通常时间复杂度较低。

缺点：

• 不一定得到全局最优解：贪心算法只能保证局部最优，不能保证全局最优。

• 需要证明正确性：在使用贪心算法时，通常需要证明它能够得到全局最优解。

二，举例

        1.最长连续递增序列：给定一个未经排序的整数数组，找到最长且连续递增的子序列，并返回该序列的长度。

public class demo01 {public static void main(String[] args) {System.out.println(findLength(new int[]{1,2,3,2,3,4,3,4,5,6,7}));}public static int findLength(int[] nums) {int start = 0;int max = 0;for (int i = 1; i < nums.length; i++) {if (nums[i] <= nums[i-1]) {start = i;}max=Math.max(max,i-start+1);}return max;}
}

        2.在柠檬水摊上，每一杯柠檬水的售价为5美元。顾客排队购买你的产品，一次购买一杯。

每位顾客只卖一杯柠檬水，然后向你付5美元、10美元或20美元。必须给每个顾客正确找零。注意，一开始你手头没有任何零钱，如果你能给每位顾客正确找零，返回为true，否则返回false。

public class demo01 {public static void main(String[] args) {System.out.println(change(new int[]{5,5,20}));}public static boolean change(int[] bills) {int five=0,ten=0;for(int i=0;i<bills.length;i++){if(bills[i]==5){five++;         //此时多了一张5块}else if(bills[i]==10){if(five==0){return false;}five--;ten++;}else{                   //来了一张20if(five>0&&ten>0){  //如果有5块和10块five--;ten--;}else if(five>=3){  //或者有三张以上的5块five-=3;}else {return false;}}}return true;}
}

        3.三角形的最大周长：给定一些正数（代表长度）组成的数组arr，返回由其中三个长度组成的、面积不为0的三角形的最大周长。如果不能形成任何面积不为0的三角形，返回0.

import java.util.Arrays;public class demo01 {public static void main(String[] args) {System.out.println(length(new int[]{3,6,2,3}));}public static int length(int[] nums) {Arrays.sort(nums);          //先排序for (int i = nums.length-1; i >=2; i--) {if (nums[i-1]+ nums[i-2]>nums[i]) {return nums[i-1]+nums[i-2]+nums[i];}}return 0;}
}