算法——贪心法（Greedy）

贪心法

• 把整个问题分解成多个步骤，在每个步骤都选取当前步骤的最优方案，直到所有步骤结束；在每一步都不考虑对后续步骤的影响，在后续步骤中也不再回头改变前面的选择。
• 不足之处：
  • 贪心算法并不能保证获得全局最优解，但总能获得局部最优解

  • 贪心算法只能确定某些问题的可行性范围

• 贪心算法可解决的问题通常大部分都有如下的特性：

  • 1、有一个以最优方式来解决的问题。为了构造问题的解决方案，有一个候选的对象的集合：比如不同面值的硬币

  • 2、随着算法的进行，将积累起其他两个集合：一个包含已经被考虑过并被选出的候选对象，另一个包含已经被考虑过但被丢弃的候选对象

  • 3、有一个函数来检查一个候选对象的集合是否提供了问题的解答。该函数不考虑此时的解决方法是否最优

  • 4、还有一个函数检查是否一个候选对象的集合是可行的，即是否可能往该集合上添加更多的候选对象以获得一个解。和上一个函数一样，此时不考虑解决方法的最优性

  • 5、选择函数可以指出哪一个剩余的候选对象最有希望构成问题的解?

  • 6、最后，目标函数给出解的值?

• 利用贪心法求解的问题应具备如下2个特征?

  • 1、贪心选择性质

    一个问题的整体最优解可通过一系列局部的最优解的选择达到，并且每次的选择可以依赖以前作出的选择，但不依赖于后面要作出的选择。

  • 2、最优子结构性质

    当一个问题的最优解包含其子问题的最优解时，称此问题具有最优子结构性质。

• 与动态规划的区别

  贪心算法与动态规划的不同在于它对每个子问题的解决方案都做出选择，不能回退。动态规划则会保存以前的运算结果，并根据以前的结果对当前进行选择，有回退功能。

一、?正整数分解使得乘积最大问题（贪心）

问题描述：

设n是一个正整数。现在要求将n分解为若干个自然数之和，且使这些自然数的乘积最大。

分析：

• 将这个大问题分解为两个小问题：

  • （1）这些自然数是互不相同的

  • （2）这些自然数可以是相同的

• 1不会增大乘积，反而会占据和，所以分解出的数中不应有 1

• 先找几个数作例子，找规律

• 注意应用到实际问题时，可能存在两个问题：

  • 1、乘积出来的数太大，题目要求返回取余后的结果即可

    • 解决办法：一边乘积，一边取余，而非全部乘积完成后取余

  • 2、分解出来的数太多，把它们乘积到一起会超时

    • 解决办法：快速幂（不用递归）

  • 见下面的第二题

1、不同的自然数

将其分解成连续的整数，从2开始，2，3，4，……将剩余的数按照从后往前的次序一次均匀分配。

package no1_1;
import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner input=new Scanner(System.in);
        int n=input.nextInt();
        int k=2; // 从2开始分解成连续的数
        // 创建一个包含100个整数的数组
        int in[]=new int[100];
        int i=0;
        // 把n分成2，3，4，……一组连续的数字
        while(n>=k) {
            in[i++]=k;
            n-=k;
            k++;
        }
        // 如果有剩余的数，从后往前加到前面分好的一组连续数字中
        if(n!=0) {
            // 如果分剩的数与上一个减数相同，先对其加1，才能保证前面的减数都能均匀分配
            if(n==in[i-1]) {
                in[i-1]++;
                n--;
            }
            // 从后往前均匀分配
            for(int j=0;j<n;j++) {
                in[i-1-j]++;
            }
        }
        // 初始化乘积result为1
        int result=1;
        // 计算最大乘积
        for(int j=0;j<=i-1;j++) {
            result*=in[j];
        }
        System.out.println(result);
    }	
}

2、可以有相同的自然数

主要将 n 分解成2和3，主要是3。

package no1_1;
import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner input=new Scanner(System.in);
        int n=input.nextInt();
        // 创建一个包含100个整数的数组
        int in[]=new int[100];
        int i=0;
        // 当n不等于2和4时，按3进行分解
        while(n!=2 && n!=4) {
            in[i++]=3;
            n-=3;
        }
        // 当n不等于0时，按2继续分解
        while(n!=0) {
            in[i++]=2;
            n-=2;
        }
        // 初始化乘积result为1
        int result=1;
        // 计算最大乘积
        for(int j=0;j<=i-1;j++) {
            result*=in[j];
        }
        System.out.println(result);
    }	
   
}

二、数的潜能（贪心）

分析

• 
• 快速幂：快速幂 - OI Wiki (oi-wiki.org)

package no1_1;
import java.util.*;
public class Main {
    public static void main(String[] args) {

        Scanner input=new Scanner(System.in);
        long n=input.nextLong();
        if(n==1) {
        	System.out.println(1);
        }else {
            long threeNums=n/3;//n最多能分出多少个3
            int result=1;
            if(n%3==1) {//分解成threeNums个3和两个2，（4是特殊的例子，拆分成两个2时，乘积最大）
            	threeNums--;
            	result=4;
            }else if(n%3==2) {//分解成threeNums个3和一个2
            	result=2;
            }   
        	result=binpow(result,3,threeNums,5218);          
            System.out.println(result);
        }        
    }	
  //使用二进制快速幂算法计算 baseNumber 的 power 次幂对 modNumber 取模的结果
    public static int binpow(int result,int baseNumber,long power,int modNumber) {
    	result%=modNumber;// 对底数取模，防止溢出
    	baseNumber%=modNumber;// 对底数取模，防止溢出
    	while(power>0) {
    		if((power&1)==1) {
    			result=result*baseNumber%modNumber;// 如果 幂 的当前位为 1，则更新结果
    		}
    		baseNumber=baseNumber*baseNumber%modNumber;// 底数自乘取模，相当于2次幂后取模
    		power>>=1;//power  右移一位
    	}
    	return result;
    }
}

三、最大分解

分析

• n=a0>a1>a2>……>ap，a(i+1)是a(i)的最大约数，
• 比如10>5>1，?5是10不等于自身的最大约数，1是5不等于自身的最大约数
• 找到每层不等于自身的最大约数即可

package no1_1;
import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner input=new Scanner(System.in);
        int n=input.nextInt();
        long sum=0;
        while(n!=1) {//当n==1时，就不能再分解下去了
        	//当i==n时，n为质数，不等于它自身的最大约数即为1
        	for(int i=2;i<=n;i++) {
    			if(n%i==0) {
    				n=n/i;
    				sum+=n;
    				break;
    			}
    		}
        }
        System.out.println(sum);
    }
}