欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

剪绳子-贪婪算法(证明选择最优)

程序员文章站 2022-07-05 21:57:44
题目:给一根长度为n的绳子,请把绳子剪成m段(m,n都是整数且1),每段绳子的长度相乘最大乘积是多少?如绳子长度为8,当分别为2,3,3时,此时最大乘积181.思路:贪婪算法,每一步都可以做出一个贪婪的选择,基于此选择,我们能得到最优解2.贪婪选择:n%3=0 12/3=4,则s=3^4=81n%3=1 13/3=4余1,此时拿出一段3和余下的1,组成4 s=3^(4-1)*(3+1)n%3=2 13/3=4余2 s=3^4*23.代码...
题目:

给一根长度为n的绳子,请把绳子剪成m段(m,n都是整数且1),每段绳子的长度相乘最大乘积是多少?如绳子长度为8,当分别为2,3,3时,此时最大乘积18

1.思路:贪婪算法,每一步都可以做出一个贪婪的选择,基于此选择,我们能得到最优解
2.贪婪选择:

剪绳子-贪婪算法(证明选择最优)

  • n%3=0

       12/3=4,则s=3^4=81
    
  • n%3=1

     	13/3=4余1,此时拿出一段3和余下的1,组成4 
     	s=3^(4-1)*(3+1)
    
  • n%3=2

     	13/3=4余2
     	s=3^4*2		
    
3.代码
 		12 =>  (3^4)*(2^0)
 		13 =>  (3^3)*(2^2)  
 		14 =>	(3^4)*(2^1)	

public class Main14 {
    public static void main(String[] args) {
        int len = new Scanner(System.in).nextInt();
        System.out.println(maxMultip(len));
    }
    private static int maxMultip(int len) {
        if (len < 2)
            return -1;
        if (len ==2)
            return 1;
        if (len == 3)
            return 2;
        int timoeOf3 = len / 3;
        if (len - 3* timoeOf3 == 1)
            timoeOf3 -= 1;
        int timeOf2 = (len - 3 * timoeOf3) / 2;
        return (int)Math.pow(3,timoeOf3)*(int)Math.pow(2,timeOf2);
    }
}

本文地址:https://blog.csdn.net/tmax52HZ/article/details/107684967