贪婪算法小结（Java版）
贪婪算法：
在每一个阶段，可以认为所做出的的决定是最好的，而不考虑将来的后果。通常，这意味着选择的是某个局部最优。当算法终止时，我们希望局部最优等于全局最优，如果是这样的话，这个算法就是正确的，否则我们将得到一个次最优解。
若我们得到的局部最优等于全局最优，则称这个问题是可绝对贪婪问题，否则它是一个近似贪婪问题，在不要求最优解时，我们可以使用此算法得到次最优解。
贪心法的设计思路：
1.创建数学模型来描述问题。
2.把求解的问题分成若干个子问题。
3.对每一子问题求解，得到子问题的局部最优解。
4.把子问题的解局部最优解合成原来解问题的一个解。
使用前提：局部最优策略能导致产生全局最优，所以谨慎使用贪心算法。
贪心算法典型例题：
1.Huffuman树 -------------来自蓝桥杯练习题BASIC-28。测试已通过
题目：
设计思路：
每次选择数组中最小的两个元素进行相加即可得到最优权值。
代码：
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）算法。