算法练习-剪绳子（贪心算法）

剪绳子问题

题目

给你一根长度为 n 的绳子，请把绳子剪成整数长度的 m 段（m、n都是整数，n>1并且m>1），每段绳子的长度记为 k[0],k[1]…k[m-1] 。请问 k[0]k[1]…*k[m-1] 可能的最大乘积是多少？例如，当绳子的长度是8时，我们把它剪成长度分别为2、3、3的三段，此时得到的最大乘积是18。

思路

贪心算法：

贪心算法（又名贪婪算法），如字面意思，只考虑当前最优解，并不从整体上去考虑最优，因此，在某种意义上它只是在局部上的最好选择。对于多数的问题而言，通过贪心算法也可以得到它的整体最优，但并不是所有，因此选择的贪心策略必须具备无后效性（即某个状态以后的过程不会影响以前的状态，只与当前状态有关。）

解题：

按照题意，绳子至少被剪一次，因此绳子最短为2

从局部最优开始

当n=2, max = 1×1

当n=3, max = 2×1

当n=4, max = 2×2 > 3×1

当n=5, max = 3×2 （此时开始，已经大于本身长度）

当n=6, max = 3×3 > 2×2×2

当n=7，max = 3×2×2 > 3×3×1

…

并且，当n大于5后，n都可以分解为2和3两个数字的和再相乘求积，所以我们每次剪绳子尽可能剪成每段长度为3，若剩余绳子长度为4时（2×2 > 3×1），无需再次分割。

Java代码

//n为绳子长度 n的值必须大于或等于2
    public static int test(int n) {
        if (n <= 3) {
            return n - 1;
        } else {
            int a = n / 3;
            int b = n % 3;
            if (b == 0) {
                return (int) Math.pow(3, a);
            } else if (b == 1) {//若余数为1，则说明最后分割前，绳子长度为4，无需再次分割
                return (int) (Math.pow(3, a - 1) * 4);
            } else {
                return (int) (Math.pow(3, a) * 2);
            }
        }

    }