A股上市公司传智教育(股票代码 003032)旗下技术交流社区北京昌平校区

 找回密码
 加入黑马

QQ登录

只需一步,快速开始

© wuyanzu 初级黑马   /  2019-9-26 15:24  /  992 人查看  /  0 人回复  /   0 人收藏 转载请遵从CC协议 禁止商业使用本文

本帖最后由 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[i] = 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]​

0 个回复

您需要登录后才可以回帖 登录 | 加入黑马