18：剪绳子

剪绳子：

一根长度为n的绳子，把绳子剪成m段，n>m>1且n>1，每段绳子的长度即为k[0],k[1]…k[m]，求k[0]*k[1]…*k[m]的最大乘积.

n是一个给定的绳子长度，m为未知

动态规划：

public class Offer19 {public static void main(String[] args) {System.out.println(maxProduct(7));}/*** 设置f(n)为绳子长度为n时的最大乘积，我们不知道剪几刀会是该绳子的最大乘积* 现假设我们在离绳头i远的位置剪一刀，分为绳子a和绳子b，a绳长度为i，b绳长度为n-i，那现在的乘积为i*n-i，但是我们不知道这是不是最大乘积。* 所以可得f(n) = max(f(i)*f(n-i))*/public static int maxProduct(int length){if(length==1)return 0;if(length==2)return 1;if(length==3)return 2;//长度为length，index最大为length-1int[] temp = new int[length+1];//数组前前三位装的是绳子剪之后可能存在的绳子的长度temp[1]=1;temp[2]=2;temp[3]=3;  int max = 0;//我们从绳子长度为4开始计算for(int i=4;i<=length;i++){max=0;//i/2的目的在于减少后面的重复for(int j=1;j<=i/2;j++){int product = temp[j]*temp[i-j];if(max<product)max=product;temp[i]=max;}}max = temp[length];return max;}
}

贪婪算法：

 public static int maxNumber(int length) {if (length < 2) {return 0;}if (length == 2) {return 1;}if (length == 3) {return 2;}// 尽可能多去剪长度为3的绳子//计算长度为3的绳子数量int timesOf3 = length / 3;// 当最后剩下长度为4 的时候，绳子长度为3的段数减一if(length - timesOf3*3 == 1){timesOf3 --;}int timesOf2 = (length - timesOf3 * 3) / 2;return (int)Math.pow(3, timesOf3) * (int ) Math.pow(2, timesOf2);}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！