题目描述
给你一根长度为n的绳子,请把绳子剪成m段 (m和n都是整数,n>1并且m>1)每段绳子的长度记为k[0],k[1],...,k[m].请问k[0]*k[1]*...*k[m]可能的最大乘积是多少?例如,当绳子的长度为8时,我们把它剪成长度分别为2,3,3的三段,此时得到的最大乘积是18.
代码实现
动态规划解法
按照从下而上的顺序计算,先得到f(2),f(3),再计算f(4),f(5),f(n)=max(f(i)xf(n-i)),0<i<n。
def dynamic_programing(n):
if n<2:
print(0)
if n==2:
print(1)
if n==3:
print(2)
l=[0,1,2,3] #l中存放着长度为i的绳子剪成若干段长度的最大乘积,i从0开始
for i in range(4,n+1):
max=0
for j in range(1,i//2+1):
temp=l[j]*l[i-j]
if temp>max:
max=temp
l.append(max)
print(l[n])
#测试
dynamic_programing(8)
输出
贪婪算法
当n>=5的时候,尽可能多的剪长度为3的绳子,将长度为n的绳子一值减到长度为4的时候,停止
def greedy_algorithm(n):
if n<2:
return 0
if n==2:
return 1
if n==3:
return 2
multi_3=0
while n>4:
multi_3+=1
n-=3
return 3**multi_3*n
print(greedy_algorithm(8))
输出