黑马程序员技术交流社区
标题: 剪绳子问题 [打印本页]
作者: wuyanzu 时间: 2019-9-26 15:24
标题: 剪绳子问题
本帖最后由 wuyanzu 于 2019-9-26 15:25 编辑
天气分享
24° 阴 空气 良
我要稿费,班主任给我稿
费
给你一根长度为n的绳子，请把绳子剪成m段（m、n都是整数，n>1并且m>1），
每段绳子的长度记为k[0],k[1],…,k[m]。请问k[0]xk[1]x…xk[m]可能的最大乘积是多少？
例如，当绳子的长度是8时，我们把它剪成长度分别为2、3、3的三段，此时得到的最大乘积是18。
思路&实现注意
当长度大于3 f[n]才能得到绳子的最大乘积
动态规划特征
从上往下分析问题，从下往上求解问题;
- 求一个问题的最优解;(最大值或者最小值)
- 问题能够分解成若干个子问题,并且子问题之间还有重叠的更小的子问题
- 分解后的小问题也存在最优解,如果把小问题的最优解组合起来能够得到整个问题的最优解,就可以使用动态规划
实现[Java] 纯文本查看 复制代码
public int cutRope(int target) {
//排除特殊情况
if (target < 2) {
return 0;
}
if (target == 2) {
return 1;
}
if (target == 3) {
return 2;
}
int[] products = new int[target + 1];
products[0] = 0;
products[1] = 1;
products[2] = 2;
products[3] = 3;
for (int i = 4; i <= target; i++) {
int max = 0;
for (int j = 1; j <= i / 2; j++) {
int product = products[j] * products[i - j];
max = Math.max(max, product);
}
products = max;
}
return products[target];
}
贪婪- 由于是乘法，那么除了1以外越多数相乘，得到的结果就越大。
- 因此从2开始考虑。但是都分成2的话必然会有奇数分成包含1的段数，因为1相当于浪费了一个乘数，所以如果最后剩1的时候我们应该将他变为3. 因此得到分成的段数长度为2，3是最好的。
- 又因为 2 2 2 < 3 * 3 说明3个2都不如2个3 ，因此应该让3 相对来说比2 多。
- 于是让该数对3相除，余数如果为2，则分为 1个2 ，N个3 为最优解，如果余数为1，则应分为2个2 ，N-1 个3 为最优解
实现
[Java] 纯文本查看 复制代码
public int cutRope(int target) {
//排除特殊情况
if (target < 2) {
return 0;
}
if (target == 2) {
return 1;
}
if (target == 3) {
return 2;
}
int timesOf3 = target / 3;
if (target - timesOf3 * 3 == 1) {
timesOf3--;
}
int timesOf2 = (target - timesOf3 * 3) / 2;
int result = (int) (Math.pow(3, timesOf3) * Math.pow(2, timesOf2));
return result;
}
递归虽然动态规划比递归不知高到那里去,因为递归有很多的重复求解情况
但是,我看互联网上,剪绳子好像没有人写递归的解法,于是…就当看个玩
思路f(n)=max(f(i)*f(n-i)) 0<i<n
实现[Java] 纯文本查看 复制代码
public int cutRope03(int target) {
if (target < 2) {
return 0;
}
if (target == 2) {
return 1;
}
if (target == 3) {
return 2;
}
return cutRope03Core(target);
}
private int cutRope03Core(int target) {
if (target < 4) {
return target;
}
int max = 0;
for (int i = 1; i <= target/2; i++) {
max = Math.max(cutRope03Core(i) * cutRope03Core(target - i), max);
}
return max;
}
[size=0em]
| 欢迎光临 黑马程序员技术交流社区 (http://bbs.itheima.com/) |
黑马程序员IT技术论坛 X3.2 |