博主在讀《算法導論》時，看到了切鋼條的自底向上的偽代碼，就分享給大家
BOTTOM-UP-CUT-ROD(p,n)
1. let r[0..n]be a new array
2. r[0] = 0
3. for j = 1 to n
4. q = 負無窮
5. for i = 1 to j
6. q = max(q, p[i]+r[j-i])
7. r[j] = q
8. return r[n]
然後，博主就根據這個偽代碼來用python實現
def cutRodDP(p, n):
r = [0]*(n+1)
r[0] = 0
for j in range(1,n+1):
q = float('-inf')
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]
n = 3
print(cutRodDP(p,n)) # 結果是8
同時，在《算法導論》裡也看到了自頂向下的偽代碼，分享給大家
MEMOIZED-CUT-ROD(p,n)
1. let r[0..n]be a new array
2. for i = 0 to n
3. r[i] = 負無窮
4. return MEMOIZED-CUT-ROD-AUX(p,n,r)
MEMOIZED-CUT-ROD-AUX(p,n,r)
5. if r[n] >= 0
6. return r[n]
7. if n == 0
8. q = 0
9. else q = 負無窮
10. for i = 1 to n
11. q = max(q, p[i]+MEMOIZED-CUT-ROD-AUX(p,n-i,r))
12. r[n]=q
13. return q
用python來實現上面的代碼
def cutTopDown(p,n):
r = [0]*(n+1)
for i in range(0, n+1):
r[i] = float('-inf')
return helper(p,n,r)
def helper(p,n,r):
if r[n] >= 0:
return r[n]
q = float('-inf')
if n == 0:
q = 0
else:
q = float('-inf')
for i in range(1, n+1):
q = max(q, p[i] + helper(p, n - i, r))
r[n] = q
return q
p = [0,1,5,8,9,10,17,17,20,24,30]
n = 3
print(cutTopDown(p,n))
獲取切割方案。
偽代碼：
EXTENDED-BOTTOM-UP-CUT-ROD(p,n)
1. let r[0..n]ands[0..n]be new arrays
2. r[0]=0
3. for j = 1 to n
4. q = 負無窮
5. for i = 1 to j
6. if q < p[i]+r[j-i]
7. q=p[i]+r[j-i]
8. s[j]=i
9. r[j]=q
10. return r and s
PRINT-CUT-ROD-SOLUTION(p,n)
11. (r,s)=EXTENDED-BOTTOM-UP-CUT-ROD(p,n)
12. while n>0
13. print s[n]
14. n=n-s[n]
根據上面的偽代碼來實現出來
def extendedBottonUp(p,n):
r = [0]*(n+1)
s = [0]*(n+1)
r[0] = 0
for j in range(1, n+1):
q = float('-inf')
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
def printCut(p,n):
(r,s) = extendedBottonUp(p,n)
while n > 0:
print(s[n])
n = n - s[n]
p = [0,1,5,8,9,10,17,17,20,24,30]
n = 4
printCut(p,n) # 結果 2,2
看到這就麻煩點個贊或者關注來支持一下！謝謝各位~~
