#
#钢条切割问题:自顶向下(由大到小)
#
#自顶向下递归实现
# def CUT_ROD(p,n):
# if n==0:
# return 0;
# q = -1000
# for i in range(1,n):
# q = max(q,p[i]+CUT_ROD(p,n-i))
# return q
#获得最大值
def max(a,b):
maxData = a;
if maxData < b:
maxData = b;
return maxData
# 备忘机制的CUT-ROD
def MEMOIZED_CUT_ROD_AUX(p, n, r):
# print("p=",p)
# print("n=",n)
# print("r=",r)
n = n - 1
if r[n] >= 0:
return r[n]
if n == 0:
q = 0
else:
q = -9999
for i in range(1, n):
# print(int(p[i]))
q = max(q, int(p[i]) + int(MEMOIZED_CUT_ROD_AUX(p,n-i,r)))
r[n] = q
return q
def MEMOIZED_CUT_ROD(p,n):
r = {}
for i in range(0,n):
r[i] = -9999
return MEMOIZED_CUT_ROD_AUX(p,n,r)
if __name__ == '__main__':
p = [1,5,8,9,10,17,17,20,24,30]
#长度 i 0 1 2 3 4 5 6 7 8 9 10
#价格 pi 0 1 5 8 9 10 17 17 20 24 30
n = 20
print("最大的收益:",MEMOIZED_CUT_ROD(p,10))