当前位置：首页 > news >正文

剪绳子 -- java

news 来源：原创 2024/4/29 9:32:09

题目描述

给你一根长度为 n 的绳子，请把绳子减成 m 段（m、n都是整数，n > 1 并且 m > 1, 每段绳子的长度记为k[0], k[1],…,k[m]。

请问k[0]*k[1]k[2]…*k[m]可能的最大乘积是多少？例如，当绳子的长度是8时，我们把它剪成的长度为2、3、3三段，此时得到的最大乘积是18。

题目考点

考察应聘者的抽象建模能力。应聘者需要把一个具体的场景抽象成一个能够用动态规划或者贪婪算法解决的模型。
考察应聘者对动态规划和贪婪算法的理解。能够灵活运用动态规划解决问题的关键是具备从上到下分析问题、从下到上解决问题的能力，而灵活运用贪婪算法则需要扎实的数学基本功。

解题思路

动态规划

设 f(n) 代表长度为n的绳子剪成若干段的最大乘积，如果第一刀下去，第一段长度是 i ，那么剩下的长度就是 n-i ，那么f(n)=max{f(i)f(n-i)}。假设f(i) 确定，我们就要继续求f(n-i)的最优解，我们可以看出剪绳子是最优解问题，其次，大问题包含小问题，并且大问题的最优解包含着小问题的最优解，所以可以使用动态规划求解问题，并且从小到大求解，把小问题的最优解记录在数组中，求大问题最优解时就可以直接获取，避免重复计算。

贪婪算法

尽可能多剪长度为 3 的绳子，并且不允许有长度为 1 的绳子出现，如果出现了，就从已经切好长度为 3 的绳子中拿出一段与长度为 1 的绳子重新组合，把它们切成两段长度为 2 的绳子。

证明：

当 n >= 5 时，所有f(n)都可以表示为3(n - 3)或者2(n - 2)，又因为3(n - 3) - 2(n - 2) = n - 5 >= 0。因此把长度大于 5 的绳子切成两段，令其中一段长度为 3 可以使得两段的乘积最大。

当 n = 4时，拆成 2 * 2 最大。

代码

动态规划

public class MaxProductAfterCutting {
    public static int maxProductAfterCutting_solution1(int length) {
        // 得到 绳子长度小于等于3的显然的最优解
        if (length < 2) {
            return 0;
        } else if (length == 2) {
            return 1;
        } else if (length == 3) {
            return 2;
        }

        //创建数组存储子问题最优解
        int[] products = new int[length+1];
        for (int i = 0; i <= 3; i++) {
            products[i] = i;
        }

        int max = 0;
        // 开始求解每一个绳子长度的最优解
        for (int i = 4; i <= length; i++) {
            max = 0;
            for (int j = 1; j <= i/2; j++) {
                int product = products[j] * products[i-j];
                if (max < product) {
                    max = product;
                }
            }
            products[i] = max;
        }

        return products[length];
    }

    // 测试
    public static void main(String[] args) {
        System.out.println(maxProductAfterCutting_solution1(8));
    }
}

贪婪算法

public class MaxProductAfterCutting {
    public static int maxProductAfterCutting_solution2(int length) {
        // 得到 绳子长度小于等于3的显然的最优解
        if (length < 2) {
            return 0;
        } else if (length == 2) {
            return 1;
        } else if (length == 3) {
            return 2;
        }

        // 尽可能多地剪去长度为3的绳子段
        int timesOf3 = length / 3;
        // 当绳子最后剩下的长度为4的时候，不能再剪去长度为3的绳子段
        // 此时更好的方法是把绳子剪成长度为2的两段，因为 2x2 > 3x1
        if ((length - timesOf3 * 3) == 1) {
             timesOf3--;
        }
        int timesOf2 = (length - timesOf3*3) / 2;
        return (int)(Math.pow(3, timesOf3)) * (int)(Math.pow(2, timesOf2));
    }

    // 测试
    public static void main(String[] args) {
        System.out.println(maxProductAfterCutting_solution2(8));
    }
}