数据结构与算法:贪心算法
1. 贪心算法的概念
所谓贪心算法是指,在对问题求解时,总是做出在当前看来是最好的选择。也就是说,不从整体最优上加以考虑,他所做出的仅是在某种意义上的局部最优解。 贪心算法没有固定的算法框架,算法设计的关键是贪心策略的选择。必须注意的是,贪心算法不是对所有问题都能得到整体最优解,选择的贪心策略必须具备无后效性,即某个状态以后的过程不会影响以前的状态,只与当前状态有关。 所以对所采用的贪心策略一定要仔细分析其是否满足无后效性。
2. 基本思路
-
建立数学模型来描述问题。 把求解的问题分成若干个子问题。 对每一子问题求解,得到子问题的局部最优解 把子问题的解局部最优解合成原来解问题的一个解。
3. 适用的问题
贪心策略适用的前提是:局部最优策略能导致产生全局最优解。也就是当算法终止的时候,局部最优等于全局最优。 因为用贪心算法只能通过解局部最优解的策略来达到全局最优解,因此,一定要注意判断问题是否适合采用贪心算法策略,找到的解是否一定是问题的最优解。 如果确定可以使用贪心算法,那一定要选择合适的贪心策略;
4.LeetCode–870 优势洗牌(田忌赛马问题)
问题描述: 给定两个大小相等的数组 A 和 B,A 相对于 B 的优势可以用满足 A[i] > B[i] 的索引 i 的数目来描述。 返回 A 的任意排列,使其相对于 B 的优势最大化。
* 输入:2 7 11 15 * 1 10 4 11 * 输出:2 11 7 15
问题分析:
-
可以每次都从A中找出大于当前B[i]的最小值,如果存在就将A[i]改写为该最小值,如果不存在将A[i]改写为数组最小值;
import java.util.Arrays; import java.util.LinkedList; import java.util.Scanner; /** * leetcode870:优势洗牌 * 给定两个大小相等的数组 A 和 B,A 相对于 B 的优势可以用满足 A[i] > B[i] * 的索引 i 的数目来描述。返回 A 的任意排列,使其相对于 B 的优势最大化。 * * 输入:2 7 11 15 * 1 10 4 11 * 输出:2 11 7 15 * */ public class TiantianTest1 { public static void main(String[] args) { //采用了ACM模式,因此需要自己写输入输出程序,将字符串解析为int数组 Scanner scanner = new Scanner(System.in); String s1= scanner.nextLine(); String s2 = scanner.nextLine(); String[] c1 = s1.split(" "); String[] c2 = s2.split(" "); int[] n1 = new int[c1.length]; int[] n2 = new int[c2.length]; for (int i=0;i<c1.length;i++){ n1[i] = Integer.parseInt(c1[i]); } for (int i=0;i<c2.length;i++){ n2[i] = Integer.parseInt(c2[i]); } int[] res = advantageCount(n1,n2); for (int a:res) { System.out.print(a+" "); } // System.out.println(Arrays.toString(advantageCount(n1,n2))); } public static int[] advantageCount(int[] A,int[] B){ LinkedList<Integer> list = new LinkedList<>(); Arrays.sort(A); for (Integer i:A){ list.add(i);//存储排序后的A数组 } //贪心策略:每一步都从A中找出比当前B[i]大的最小值(田忌赛马) for (int i=0;i<B.length;i++){ A[i] = findMin(list,B[i]); } //对于找不到比B[i]大的情况,A[i]取最小值 for (int i = 0; i < A.length; i++) { if (A[i]==-1){ A[i] = list.get(0); list.remove(0); } } return A; } //该函数从A中找到大于B[i]的最小值 public static int findMin(LinkedList<Integer> list,int x){ for (Integer i:list) { if (i>x){ list.remove(i); return i; } } return -1; } }
下一篇:
质数筛选-筛选1-n的质数