Blogger reading 《 Introduction to algorithms 》 when , See the bottom-up pseudo code for cutting steel bars , Let's share
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 = Negative infinity
5. for i = 1 to j
6. q = max(q, p[i]+r[j-i])
7. r[j] = q
8. return r[n]
then , Bloggers use it based on this pseudo code python Realization
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)) # The result is 8
meanwhile , stay 《 Introduction to algorithms 》 You can also see top-down pseudo code in , Share with you
MEMOIZED-CUT-ROD(p,n)
1. let r[0..n]be a new array
2. for i = 0 to n
3. r[i] = Negative infinity
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 = Negative infinity
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
use python To implement the above code
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))
Get cutting scheme .
Pseudo code ：
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 = Negative infinity
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]
According to the above pseudo code to achieve
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) # result 2,2
If you see this, please point a like or concern to support it ！ Thank you ~~
