问题描述:给你一根长度为n的绳子,请把绳子剪成m段(m和n都是整数,n>1并且m>1), 每段绳子的长度记为k[0],k[1],...,k[m]. 请问k[0]*k[1]*...*k[m]可能的最大乘积是多少?
首先本题可以用贪婪算法和动态规划算法求解,虽然贪婪算法的时间复杂度和空间复杂度都比动态规划算法要小,但是要求有一定数学基础,需要定制合理的贪婪策略(面试的时候如果换一道题一般情况下想不出来的),所以个人感觉贪婪算法在本题中没有参考价值,故本题用动态规划的方法来求解。
本方法思想:用动态规划自下而上的计算,先算出n为1、2、3。。的最大乘积,知道小的以后在去算更大的乘积。比如n为4时候最大的可能只能在1*3,2*2之间取得;n为5时,只能在f(1)*f(4),f(2)*f(3)之间取得,而f(2),f(3),f(4)之前均已经求出。
持续更新...
代码附下
Java实现:
package 剪绳子;
/**
* 给你一根长度为n的绳子,请把绳子剪成m段(m和n都是整数,n>1并且m>1) 每段绳子的长度记为k[0],k[1],...,k[m].
* 请问k[0]*k[1]*...*k[m]可能的最大乘积是多少?
* @author user 动态规划
*/
public class Test {
public static void main(String[] args) {
int len = 10;
System.out.println(maxLen(len));
}
/**
* @param len绳子的长度
* @return
*/
private static double maxLen(int len) {
// lenCut[i]表示长度为i个的最优解 lenCut[3]比较特殊
double lenCut[] = new double[len + 1];
lenCut[0] = 0;
lenCut[1] = 1;
lenCut[2] = 2;
lenCut[3] = 3;
//初始化到3是因為3>1*2,其本身比分割的大,所以當分割比3大的數字時候,如5可以分成2,3,3就不繼續往下分割了
if (len < 2) {
return 0;
} else if (len == 2) {
return 1;
} else if (len == 3) {
return 2;
} else {
for (int i = 4; i <= len; i++) {
double max = 0;
for (int j = 1; j <= i / 2; j++) {
double temp = lenCut[j] * lenCut[i - j];
if (max < temp) {
max = temp;
}
}
lenCut[i] = max;
}
}
return lenCut[len];
}
}
持续更新...欢迎赞赏!
https://blog.csdn.net/ustcer_93lk/article/details/80369712
如果有问题,欢迎大家留言,有更好的方法也期待大家告知。