贪婪算法小结（Java版）

矫情吗；* 2022-03-15 12:48 261阅读 0赞

**贪婪算法：**  
在每一个阶段，可以认为所做出的的决定是最好的，而不考虑将来的后果。通常，这意味着选择的是某个局部最优。当算法终止时，我们希望局部最优等于全局最优，如果是这样的话，这个算法就是正确的，否则我们将得到一个**次最优解**。  
若我们得到的局部最优等于全局最优，则称这个问题是**可绝对贪婪问题**，否则它是一个**近似贪婪问题**，在不要求最优解时，我们可以使用此算法得到**次最优解**。

**贪心法的设计思路：**  
1.创建数学模型来描述问题。  
2.把求解的问题分成若干个子问题。  
3.对每一子问题求解，得到子问题的局部最优解。  
4.把子问题的解局部最优解合成原来解问题的一个解。  
**使用前提**：**局部最优策略能导致产生全局最优**，所以谨慎使用贪心算法。

贪心算法典型例题：  
1.**Huffuman树** \-------------来自蓝桥杯练习题BASIC-28。测试已通过  
**题目：**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpMTM3NjQxNzUzOQ_size_16_color_FFFFFF_t_70]  
设计思路：  
每次选择数组中最小的两个元素进行相加即可得到最优权值。  
代码：

public class HuffmanTree {
    	/**
    	 * 使用递归贪心计算每一次的最小权值。
    	 * @param arr	需要计算最小权值的数组
    	 * @param result 初始结果，一般传入0
    	 * @return	返回最小权值
    	 */
    	public static int minPrice(int[] arr,int result) {
    		if(arr.length == 1)
    			return result;
    		int min1 = 0,min2 = 0;
    		Arrays.sort(arr);
    		min1 = arr[0];
    		min2 = arr[1];
    		int[] temp = new int[arr.length-1];
    		for(int i =0;i<temp.length - 1;i++) {
    			temp[i] = arr[i+2];
    		}
    		temp[temp.length-1] = min1+min2;
    		result += min1 +min2;
    		return minPrice(temp,result);
    	}
    	public static void main(String[] args) {
    		int n;
    		Scanner sc = new Scanner(System.in);
    		n = sc.nextInt();
    		int[] arr = new int[n];
    		for(int i =0;i<n;i++) {
    			arr[i] = sc.nextInt();
    		}
    		sc.close();
    		System.out.println(minPrice(arr,0));
    	}
    
    }

2.**数列极差**  
题目：n个正整数拍成的一个数列，进行如下操作：  
每次擦去其中两个数a,b，然后加入a\*b+1，直到只剩下一个数。按照这样方法得到的数中最大的为max，最小的为min，m = max - min。m就是该数列的极差，输出m  
**设计思路**：此问题与Huffman树问题相似，如果每次计算的是数组中最小的两个值，则得到的结果是最大的，反之的到的结果则是最小的。  
**代码**：

public class RangeOfPoles {
    	public static int getRange(int[] nums) {
    		int[] arr = new int[nums.length];
    		for(int i = 0;i<nums.length;i++) {
    			arr[i] = nums[i];
    		}
    		return max(nums) - min(arr);
    	}
    	
    	public static int max(int arr[]) {
    		Arrays.sort(arr);
    		int i = 0;
    		for(;i<arr.length;i++) {
    			if(arr[i] != -1)
    				break;
    		}
    		if(i == arr.length-1)
    			return arr[arr.length-1];
    		else {
    			arr[i+1] = arr[i] * arr[i+1] + 1;
    			arr[i] = -1;
    			return max(arr);
    		}
    	}
    	
    	public static int min(int arr[]) {
    		Arrays.sort(arr);
    		int i = 0;
    		for(;i<arr.length;i++) {
    			if(arr[i] != -1)
    				break;
    		}
    		if(i == arr.length-1)
    			return arr[arr.length-1];
    		else {
    			arr[arr.length-1] = arr[arr.length-2] * arr[arr.length-1] + 1;
    			arr[arr.length-2] = -1;
    			return min(arr);
    		}
    	}
    
    	public static void main(String[] args) {
    		int n;
    		Scanner sc = new Scanner(System.in);
    		n = sc.nextInt();
    		int[] arr = new int[n];
    		for(int i = 0;i<arr.length;i++) {
    			arr[i] = sc.nextInt();
    		}
    		sc.close();
    		System.out.println("数列的极差是：" + getRange(arr));
    	}
    
    }
    /**
     * 9
     * 1 2 3 4 5 6 7 8 9
     * output:数列的极差是：293747
     */

3.**重组整数**  
**题目**：键盘输入一个高精度的正整数n,去掉其中任意s个数字后剩下的数组按与按顺序组成一个新的正整数。编程，对给定的n和s，寻找一种方案使得剩下数字数组成的新数最小。输出组成的新的正整数n(n不超过240位)  
**设计思路**：  
1.因为键盘输入的是一个高精度的正整数，所以用需要将整数按位存在数组中。  
2.每次删除某位数，我们总是删除高位比较大的，所以每次比较相邻的两位，如果高位大，则删除他，否则往下比较。  
3.可能出现某次删除后，不存在高位比低位大的情况，这时，我们选择删除最低位。  
**实现代码：**

public class newNum {
    	
    	public static void Print(int[]arr) {		//从数组第一位不为零开始输出
    		int i = 0;
    		for(;i<arr.length;i++) {
    			if(arr[i]!=0)
    				break;
    		}
    		if(i == arr.length) {
    			System.out.println("0");
    			return;
    		}
    		for(;i<arr.length;i++) {
    			System.out.print(arr[i]);
    		}
    	}
    	
    	public static void change(int[] arr,int s) {
    		if(s == 0) {							//s为零说明达到要求，输出
    			Print(arr);
    			return;
    		}
    		int[] temp = new int[arr.length-1];		//新建数组存储删掉一位后的数
    		int i = 0;
    		while(i<arr.length-1) {
    			while(arr[i]<=arr[i+1]) {			//寻找相邻且前面比后面大的位置
    				i++;
    				if(i == arr.length-1)			
    					break;
    			}
    			if(i<arr.length-1) {				//如果有此种情况则删除该位置上的数
    				Delete(arr,i,temp);
    				change(temp,s-1);				//递归进行下一次操作，s--
    				return;
    			}
    			else {
    				Delete(arr,arr.length-1,temp);	//否则删除整数最后一位
    				change(temp,s-1);				//递归进行下一次
    				return;
    			}
    		}
    	}
    	public static void Delete(int[] arr,int n,int[]temp) {
    		int j = 0;
    		for(int i = 0;i<temp.length;i++) {
    			if(i == n)
    				j++;
    			temp[i] = arr[j];
    			j++;
    		}
    	}
    	public static void main(String[] args) {
    		String	s = new String();
    		Scanner sc = new Scanner(System.in);
    		s = sc.nextLine();
    		int n;
    		n = sc.nextInt();
    		sc.close();
    		char[] num = s.toCharArray();
    		int[] nums = new int[num.length];
    		for(int i = 0,j = 0;i<nums.length;i++,j++) {
    			nums[i] = (int)(num[j] - '0');
    		}
    		change(nums,n);
    	}
    
    }

4.**埃及分数**  
**题目**：设计一个算法，把一个真分数表示为埃及分数之和的形式。所谓埃及分数，是指分子数为1的分数：7/8 = 1/2+1/3+1/24  
**设计思想** ：  
设分子为a,分母为b；  
把B除以A的商+1作为新的分母C  
输出1/C  
A乘以C减去B作为新的A  
B乘以C作为新的B  
如果A大于1且能整除B，则最后一个分母为B/A  
否则循环  
**实现代码：**

public static void main(String[] args) {
    		int mol,den;
    		Scanner sc = new Scanner(System.in);
    		mol = sc.nextInt();
    		den = sc.nextInt();
    		sc.close();
    		if(mol>=den)
    			System.out.println("Input Error!!!");
    		System.out.print(mol + "/" + den + "=");
    		if(mol == 1)
    			System.out.println(mol + "/" + den);
    		else {
    			while(mol != 1) {
    				int newden = den/mol + 1;
    				System.out.print("1/" + newden);
    				mol = mol*newden-den;
    				den = den*newden;
    				if(mol>1) {
    					System.out.print("+");
    				}
    				if(den % mol == 0 || mol == 1) {
    					System.out.print("1/" +den/mol);
    					mol = 1;
    				}
    			}
    		}
    	}

可以使用贪婪算法的问题不多，如果可以使用贪婪算法，那么很大可能上贪婪算法是此题的最高效算法。但一般问题可以使用贪婪算法进行解题的很少，使用时一定要先保证他的局部最优是全局最优。还有一些例如**找零问题**和**装箱**问题使用贪心算法可能得不到最优解的，接下来会介绍动态规划（俗称DP）算法。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpMTM3NjQxNzUzOQ_size_16_color_FFFFFF_t_70]: /images/20220315/adbc8e9ef7ef40dc97bcb2271e856d52.png