给你一根长度为 n 的绳子,请把绳子剪成 m 段(m、n 都是整数,并且)。每段的绳子的长度记为、、……、。可能的最大乘积是多少?例如当绳子的长度是 8 时,我们把它剪成长度分别为 2、3、3 的三段,此时得到最大的乘积 18。
解析:该题可以用动态规划的思路解,也可以用贪心算法的思路解。
动态规划的话,首先看满不满足这两个经典的条件:大问题可以分解为若干个小的子问题,而且子问题需要大量的重复计算。这两个条件在这里都是满足的:例如绳子的长度是 12 的时候,一刀切下去变成 2 和 10,10 就成了一个子问题。10 还需要一刀切下去变成 2 和 8,这样 2 就重复了一次。虽说把 12 切成 2 和 10 不一定是最好的方案,但是我的目的在于证明子问题是有重复情况发生的。这个时候可以把子问题得到的结果提前记录下来,从而尽量避免无意义的重复,写法也就不是函数递归了,能够获得比较好的算法。在确定可以使用动态规划的时候,我们需要明确自己的目的:我们要找到最优的子问题划分。把 12 切成 2 和 10 好呢,还是切成 3 和 9 好呢?显然,,所以选择 3 和 9 比 2 和 10 要好。但是 3 和 9 就一定是最好的吗?,那么 4 和 8 就一定最好吗?你会发现,从上到下的分析,并不容易得到正确答案。那么我们应该换一种思路,从下到上的分析:
- 假设绳子总共有 2 厘米长,由于必须剪一刀,乘积是 1。
- 假设绳子总共有 3 厘米长,那么乘积是 2。
- 假设绳子总共有 4 厘米长,剪成 2 和 2 要比 1 和 3 强,乘积是 4。注意,我们可以只剪一刀,这样子条件已经满足了,剪出来的 3 不需要再剪一刀了,因为再剪一刀反而让乘积变小了。
- 假设绳子总共有 5 厘米长,剪成 2 和 3 要比 1 和 4 强。同样,剪出来的 3 和 4 不需要再剪一刀了,因为再剪一刀反而让乘积变小了。
- 假设绳子总共有 6 厘米长,剪成 3 和 3 要比 2 和 4 强。
分析到这里的时候,我们其实已经有一些子问题的结果了。剪出来的绳子片段:
- 长度为 1 的时候,它最高能贡献的乘积因子是 1;
- 长度为 2 的时候,它最高能贡献的乘积因子是 2;
- 长度为 3 的时候,它最高能贡献的乘积因子是 3,因为之前已经剪过一刀了,所以不需要把 3 再剪一次;
- 长度为 4 的时候,它最高能贡献的乘积因子是 4,这个时候多剪一刀与不剪是没区别的;
- 长度为 5 的时候,它最高能贡献的乘积因子是 6,如果这个片段不剪的话能贡献 5,剪了的话能贡献 ,当然选择再剪一刀;
- 长度为 6 的时候,它最高能贡献的乘积因子是 9,不剪的话能贡献 6,剪了的话能贡献 ,当然选择再剪一刀;
- ……
发现没有,上面的剩余长度为 4 的问题,可以理解成两个剩余长度为 2 的乘积;剩余长度为 5 的问题,可以理解为两个剩余长度为 2 和 3 的乘积;剩余长度为 6 的问题,可以理解为两个剩余长度为 3 的乘积……如果用函数的思想,用代表绳子剩余长度为 n 的时候能够提供的最大贡献,那么,,,,,……
我们在确定、、的值的时候,是通过比较两个子问题乘积的更大值来得到的。例如在判定的时候,,也可以是,这两种情况中前者更大,所以选择前者的方案。更一般的,我们考虑,我们比较的过程是,,,,……,这么多结果中最大的那一个。在刚刚的考虑过程中,、这些值在之前的计算已经记录了结果,所以我们直接用就好。
分析到这一步了,你是不是已经很清楚动态规划的代码该怎么写了?
// ====================动态规划====================
int maxProductAfterCutting_solution1(int length)
{
if (length < 2) return 0;
else if (length == 2) return 1;
else if (length == 3) return 2;
else if (length >= 4)
{
int product[length+1];
product[0] = 0; //这个其实写不写都行,后面的代码也用不到这个
product[1] = 1; //这个也用不到
product[2] = 2; //这里的 2 指的是剩下了一段长度为 2 的绳子,可以不剪
product[3] = 3; //这里的 3 指的是剩下了一段长度为 3 的绳子,可以不剪
int max = 0;
for (int i=4; i<=length; ++i)
{
max = 0;
for (int j=2; j<=i/2; ++j) //从 2 开始比较
{
if (max < product[j]*product[i-j])
max = product[j]*product[i-j]; //比较出最大的那个情况
}
product[i] = max; //记录下来
}
return product[length]; //这个时候从 0 到 n 的最优情况都记录下来了
}
return 0;
}
下一个思路是贪心算法。在使用贪心算法的时候,我们同样需要提供一些数学证明,来证明可以用贪心的思路解题。同样的,
- 假设绳子总共有 2 厘米长,由于必须剪一刀,乘积是 1。
- 假设绳子总共有 3 厘米长,那么乘积是 2。
- 假设绳子总共有 4 厘米长,剪成 2 和 2 要比 1 和 3 强,乘积是 4。
- 假设绳子长度大于 5 厘米,即 ,我们可以证明。因此切比不切强,而且切成 3 的情况比切成 2 的情况贡献的乘积多,我们应该尽量多切成 3 的片段。
因此,思路就很简单了:如果把绳子尽可能多的切成若干个 3 的片段,剩下来的长度可能是 1、2,如果少切一刀的话,也会剩下 4、5、6。为什么考虑少切一刀的情况呢?我们来看一下:
- 如果切到最后剩下了长度为 6 的片段,再切出来一段 3,剩余 3,能多乘 9,那就切;
- 如果切到最后剩下了长度为 5 的片段,再切出来一段3,剩余 2,能多乘 6,那就切;
- 如果切到最后剩下了长度为 4 的片段,再切出来一段3,剩余 1,能多乘 3;但是如果不切的话,能多乘 4!
那么这个剩余长度是 4 的情况就是特殊情况:如果剩余长度为 4,那么选择不切,而不是切成 1 和 3。到这里,算法就能写出来了:
// ====================贪心算法====================
int maxProductAfterCutting_solution2(int length)
{
if (length < 2) return 0;
else if (length == 2) return 1;
else if (length == 3) return 2;
else
{
int piecesOfThree = length/3;
//pow 函数的结果是 double 类型,所以使用类型转换:
int productOfThrees = static_cast<int>(pow(3, piecesOfThree));
if (length%3==0) return productOfThrees;
else if (length%3==2) return 2*productOfThrees;
else return productOfThrees/3*4;
}
}