动态规划 算法导论 钢铁切割 部分Python代码

#带备忘
def Memoized_cut_rod(p,n):
    r=[]
    for i in range(n+1):
        r.append(-999)
    return Memoized_cut_rod_aux(p, n,r)
def Memoized_cut_rod_aux(p,n,r):
    if r[n]>=0:
        return r[n]
    if n==0:
        q=0
    else:
        q=-1
        for i in range(1,n+1):
            q=max(q,p[i]+Memoized_cut_rod_aux(p,n-i,r))
    r[n]=q
    return q
p=[0,1,5,8,9,10,17,17,20,24,30]

def cut_Rod(p,n):
    # 普通递归实现
    if n==0:
        return 0
    q=0
    for i in range (1,n+1):
        q=max(q,price[i]+cut_Rod(price,n-i))
    return q
price=[0,1,5,8,9,10,17,17,20,24,30] # 切一根 价格为1 2 为5
print(cut_Rod(price,9),"递归实现")
print(Memoized_cut_rod(p,9),"带备忘，自顶向下")

### 自低向下
def bottom_up_cut_rod(p,n):
    r=[-99 for i in range(n+1)]
    r[0]=0
    for j in range(1,n+1):
        q=0
        for i in range(1,j+1):
            q=max(q,p[i]+r[j-i])
        r[j]=q
    return r[n]
p=[0,1,5,8,9,10,17,17,20,24,30]
print(bottom_up_cut_rod(p,4))

def extend_bottom_up_cut_rod(p,n):
    r=[-1 for i in range(n+1)]
    s=[-1 for i in range(n+1)]
    r[0]=0
    for j in range(1,n+1):
        q=0
        for i in range(1,j+1):
            if q < p[i]+r[j-i]:
                q=p[i]+r[j-i]
                s[j]=i
        r[j]=q



    return r, s
p=[0,1,5,8,9,10,17,17,20,24,30]
print(extend_bottom_up_cut_rod(p,4),"优化 的自底向上")
def Print_cut_rod_solution (p,n):
    (r,s)=extend_bottom_up_cut_rod(p,n)
    print("\n价格",r,"\n 长度",s,"输出各切割方案\n")
    while n>0:
        n=n-s[n]
    print(r)
Print_cut_rod_solution(p,10)