剪绳子

xiaoxiao2021-02-28  146

声明:题目和程序来自《剑指offer》,注释和分析为自己所写备忘,侵删。

动态规划

题目:给你一根长度为n的绳子,请把绳子剪成m段(mn都是整数,n>1并且m>1),每段绳子的长度记为k[0],k[1],,k[m]。请问k[0] x k[1] xx k[m]可能的最大乘积是多少?例如,当绳子的长度是8时,我们把它剪成长度分别为2, 3, 3的三段,此时得到的最大乘积是18

分析:动态规划,POJ上有好多这种题,主要是考虑能否将大问题可以化为几个小问题的集合,一般是化为两个小问题。在能够划分成小问题之后,再考虑是否需要存储划分的路径,怎么存储,是否需要存储小问题的解以加快计算速度等。

对于这个题,f(n) = max( f(i) x f(n-i)), 0<i<n

贪婪算法:不同于动态规划的遍历,贪婪每一步都求出对于当前步最优的解,不需要考虑前一步和后一步。贪婪算法的对最优解得判断是由数学方式计算的。

动态规划解题思路:

int maxProductAfterCutting_solution(int length) { if(length <2)//长度最小为2 return 0; if(length ==2) return 1;//长度等于2的解 if(lentgh ==3) return 2;//长度等于3的解 int* products = new int[length + 1];//存放最优解得矩阵 products[0] = 0; products[1] = 1; products[2] = 1; products[3] = 2; int max = 0; for(int i=4;i <=length; i++){//从4开始求最大值,这里没有在划分m的条件下,也没有存储最大的划分方式,只是单单求最大值。 max = 0; for(j = 1; j<=i/2; j++){ int temp = products[j] *products[i-j]; if(max <temp) max = temp; products[i] = max; }//求products[i]的最大值 } max = products[length]; delete[] products; return max; }

 

贪婪算法代码:

(当绳子长度>=5时,尽可能多的剪长度为3的绳子,当剩下长度为4时,将绳子剪为两段长度为2的绳子)

int maxProductAfterCutting(int length) { if(length<2) return 0; if(length == 2) return 1; if(length == 3) return 2; int timesOf3 = length/3; if(length - timesOf3 * 3 ==1)//剩余长度为4时,剪成2x2的 timeOf3 -= 1; int timeOf2 = (length -timesOf3*3)/2; return (int)(pow(3, timesOf3))*(int)(pow(2, timesOf2)); }

贪婪算法依据:

绳长n>=5时,2n - 2> n,且3n - 3> n,且3n - 3> 2n - 2)。在f(n) = f(i)*f(n - i)的情况下,分成3n-3的乘积最大。为什么这样分?在n>7时分成4n - 4)不更大吗?或者5(n - 5),并不是,5(n-5)可以比2*3(n-5)小,4n - 4)等同于2*2n-4),其他6(n-6)同理。至于这个公式怎么想到的,在考虑动态规划时,想到划分1n - 1)、2n - 2)、3n - 3)、4n - 4)、5n - 5),但是从4开始都可以拆为2,3组合,且2,3组合大于单个数字,根据f(n) = f(i)*f(n-i),考虑将所有的化为2,3 组合。

这种前提下是没有限定划分段数m,仅求最大数,若段数m限定,可以根据

直接求解。

 

 

 

转载请注明原文地址: https://www.6miu.com/read-2250225.html

最新回复(0)