#
#钢条切割问题:自低向上(由小到大)
#
#获得最大值
def max(a,b):
maxData = a;
if maxData < b:
maxData = b;
return maxData
def BOTTOM_UP_CUT_ROD(p,n):
r = {}
r[0] = 0
for j in range(1,n):
q = 0
for i in range(1,j):
q = max(int(q),int(p[i] + r[j - i]))
r[j] = q
return r[n-1],r
if __name__ == '__main__':
p = [1,5,8,9,10,17,17,20,24,30]
# for i in range(0,9):
#长度 i 1 2 3 4 5 6 7 8 9 10
#价格 pi 1 5 8 9 10 17 17 20 24 30
print("最大的收益:",BOTTOM_UP_CUT_ROD(p,4))
``