江苏龙网

  1. 主页 > 生活百科 > >

经典算法——剪绳子

算法

剪绳子给你一根长度为n的绳子，请把绳子剪成整数长的m段(m、n都是整数，n>1并且m>1,m<=n),每段绳子的长度记为k[1],...k[m] 。请问k[1]*...*k[m]可能的最大乘积是多少？
例如，当绳子的长度为8时，我们把它剪成长度分别为2、3、3的三段，此时得到的最大乘积是18.
贪心法public int cutRope(int target){//42*2//52*3//63*3//72*2*34*3//82*3*3//93*3*3//102*2*3*3 4*3*3//112*3*3*3//由以上举的例子可以看出，最后情况只可能为2或3//由3(n-3)>=2(n-2)，可知当n=5时，等式相等，当n>5时，应让3尽量的多 。if(target<2){return 0;}if(target==2){//由题目知m>1,所以2为1*1=1return 1;}if(target==3){//m>1,所以3为2*1=1return 2;}if(target%3==0){//当绳子长刚好为3的倍数，则结果为3的（target/3）次幂return (int)Math.pow(3,target/3);}else if(target%3==1){//当绳子长对3取余刚好等于1时，可以多留出一个3，结果就为3的（target/3-1）次幂乘以4return 4*(int)Math.pow(3,target/3-1);}else{//当绳子长对3取余刚好等于2时，留出2，结果就为3的（target/3）次幂乘以2return 2*(int)Math.pow(3,target/3);}}public static void main(String[] args) {System.out.println(cutRope(8));//18System.out.println(cutRope(9));//27}动态规划法//一个比较简单的动态规划//求问题最优解，该问题可以分成若干个子问题，子问题之间还有重叠的更小的子问题，考虑使用动态规划 。//以自上而下分析，在长度为n的绳子剪下乘积为f(n),剪下i长度后，还剩n-i，即得公式//f(n)=max(f(i)*f(n-i))//为了避免重复计算子问题，以从下往上的顺序计算小问题的解并保存下来，在以此为基础求解更大问题 。//每public int cutRope(int target){if(target<2){return 0;}if(target==2){return 1;}if(target==3){return 2;}int []dp=new int[target+1];dp[1]=1;dp[2]=2;dp[3]=3;//1 2 3 都是不剪绳子，得到的乘积最大int res=0;//记录每次剪完的最大值for (int i=4;i<=target;i++){for (int j=1;j<=i/2;j++){//要计算j*i-j的最大值，所以只用计算j<=i的值res=Math.max(res,dp[j]*dp[i-j]);//得到长度为i时，所有剪法的最大值}dp[i]=res;//得到当前剪法的最大值，保存到dp数组中}return dp[target];//返回最大值}public static void main(String[] args) {System.out.println(cutRope(8));//18System.out.println(cutRope(9));//27}
【经典算法——剪绳子】


    推荐阅读


    上一篇：兰贵人茶叶有什么作用,茶叶水洗脸有什么好处

    下一篇：红茶曙光已现,果味养生红茶