洛谷P1249 最大乘积 java两种解法

素颜马尾好姑娘i 2023-01-11 08:51 179阅读 0赞

# 洛谷P1249 最大乘积 java两种解法 #

## 方法一、动态规划 ##

看到题目，我们可以将题目抽象成01背包问题，背包容量为n，价值是装的物品体积的乘积。但因为大数模拟，而java大数类比较慢，所以此方法会造成超时，但也是一种可行思路。  
**代码描述:**

import java.math.BigInteger;
    import java.util.*;
    public class Main {
        
    	public static void main(String[] args) {
        
    		//题目可以转换成01背包问题
    		Scanner sc=new Scanner(System.in);
    		int n=sc.nextInt();
    		if(n==3) {
        
    			System.out.print(1+" "+2);
    			System.out.println();
    			System.out.print(2);
    			return ;
    		}
    		else if(n==4) {
        
    			System.out.print(1+" "+3);
    			System.out.println();
    			System.out.print(3);
    			return ;
    		}
    		
    		BigInteger[][]dp=new BigInteger[n+1][2];
    		for(int i=0;i<n+1;i++) {
        
    			for(int j=0;j<2;j++) {
        
    				dp[i][j]=new BigInteger("0");
    			}
    		}
    		dp[0][0]=new BigInteger("1");
    		dp[0][1]=new BigInteger("0");
    		dp[1][0]=new BigInteger("1");
    		dp[1][1]=new BigInteger("1");
    		dp[2][0]=new BigInteger("2");
    		dp[2][1]=new BigInteger("2");
    		dp[3][0]=new BigInteger("2");
    		dp[3][1]=new BigInteger("2");
    		for(int i=3;i<=n;i++) {
        
    			for(int j=n;j>=i;j--) {
        
    				BigInteger cur=new BigInteger(Integer.valueOf(i).toString());
    				BigInteger next=dp[j-i][0].multiply(cur);
    				if(dp[j][0].compareTo(next)>=0)  continue;
    				else {
        
    					dp[j][0]=next;
    					dp[j][1]=new BigInteger(Integer.valueOf(i).toString());
    				}
    			}
    		}
    		BigInteger ret=dp[n][0];
    		
    		ArrayList<Integer> arr=new ArrayList<Integer>();
    		while(n!=new Integer(dp[n][1].toString())) {
        
    			arr.add(new Integer(dp[n][1].toString()));
    			n=n-new Integer(dp[n][1].toString());
    		}
    		arr.add(new Integer(dp[n][1].toString()));
    		Collections.sort(arr);
    		System.out.print(arr.get(0));
    		for(int i=1;i<arr.size();i++) {
        
    			System.out.print(" "+arr.get(i));
    		}
    		System.out.println();
    		System.out.print(ret);
    		return;
    	}
    }

## 方法二、贪心算法 ##

**基本思路:**

本题要先用简单的数论和贪心找到最优解的组成方法，再用高精度乘法求积。
     
    以2004为例，由于把2004分拆成若干个互不相等的自然数的和的分法只有有限种，因而一定存在一种分法,使得这些自然数的乘积最大。
     
    若1作因数,则显然乘积不会最大。把2004分拆成若干个互不相等的自然数的和,因数个数越多，乘积越大。为了使因数个数尽可能地多，我们把2004分成2+3…+n直到和大于等于2004。
     
    若和比2004大1，则因数个数至少减少1个，为了使乘积最大,应去掉最小的2，并将最后一个数（最大）加上1。
     
    若和比2004大k（k≠1）,则去掉等于k的那个数,便可使乘积最大。
     
    例如15：s=2+3+4+5+6刚好大于15，s-15=5，所以把5去掉。
     
    又例如13：s=2+3+4+5刚好大于13，s-13=1,所以去掉2，并把5加1，即3 4 6。

**证明**  
因本人能力有限,此思路参考洛谷题解中思路。对于证明方法,本人也没有完全理解，仅仅能够理解对一个数分解的越多其乘积越大，而在舍去时则不太理解。贴一下java代码

import java.math.BigInteger;
    import java.util.*;
    public class Main {
        
    	public static void main(String[] args) {
        
    		//贪心+高精度求解
    		Scanner sc=new Scanner(System.in);
    		int n=sc.nextInt();
    		
    		if(n==3) {
        
    			System.out.print(1+" "+2);
    			System.out.println();
    			System.out.print(2);
    			return;
    		}
    		
    		int[] ret=new int [10001];
    		int sum=0;
    		int i=1;
    		int index=0;
    		while(sum<n) {
        
    			i++;
    			sum+=i;
    			ret[index]=i;
    			index++;
    		}
    		ArrayList<Integer> arr=new ArrayList<Integer>();
    		BigInteger big=new BigInteger("1");
    		if(sum-n==1) {
        
    			ret[index-1]+=1;
    			for(int j=1;j<index;j++) {
        
    				arr.add(ret[j]);
    			}
    		}
    		else if(sum-n>1){
        
    			int cur=sum-n;
    			for(int j=0;j<index;j++) {
        
    				if(ret[j]!=cur) arr.add(ret[j]);
    			}
    		}
    		else {
        
    			for(int j=0;j<index;j++) {
        
    				arr.add(ret[j]);
    			}
    		}
    		boolean flag=false;
    		for(Integer o:arr) {
        
    			if(flag) System.out.print(" "+o);
    			else {
        
    				System.out.print(o);
    				flag=true;
    			}
    			big=big.multiply(new BigInteger(Integer.valueOf(o).toString()));
    		}
    		System.out.println();
    		System.out.print(big);
    		return;
    	}
    }