Rod Cutting

1 P.363

def CUT_ROD(p, n):
    if n == 0:
        return 0
    q = -1
    for i in range(1, n+1):
        q = max(q, p[i] + CUT_ROD(p, n-i))
    return q

def main():
    p = [0, 1, 5, 8, 9, 10, 17, 17, 20, 24, 30]
    for i in range(1, len(p)):
        print('the max profit of n = %i is: ' %i, CUT_ROD(p, i))

main()

Output-1

2 P.366

def BOTTOM_UP_CUT_ROD(p, n):
    r = [0] * (n+1)
    for i in range(1, n+1):
        q = -1
        for j in range(1, i+1):
            q = max(q, p[j] + r[i-j])
        r[i] = q
    return r[n]

def main():
    p = [0, 1, 5, 8, 9, 10, 17, 17, 20, 24, 30]
    for i in range(1, len(p)):
        print('the max profit of n = %i is: ' %i, BOTTOM_UP_CUT_ROD(p, i))

main()

Output-2

3 P.369

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

def PRINT_CUT_ROD_SOLUTION(p, n):
    r, s = EXTEDNED_BOTTOM_UP_CUT_ROD(p, n)
    print('the max profit of n = %i is: %i' %(n,r[n]))
    print('the sulution of max profit is: ', end = '')
    while n > 0:
        print(s[n], end = '\t')
        n = n - s[n]

def main():
    p = [0, 1, 5, 8, 9, 10, 17, 17, 20, 24, 30]
    for i in range(1, len(p)):
        PRINT_CUT_ROD_SOLUTION(p, i)
        print('\n')

main()

Output-3

4 P.365~P.366

def MEMOIZED_CUT_ROD(p, n):
    r = [-1] * (n+1)
    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

def main():
    p = [0, 1, 5, 8, 9, 10, 17, 17, 20, 24, 30]
    for i in range(1, len(p)):
        print('the max profict of n = %i is: ' %i, MEMOIZED_CUT_ROD(p, i))

main()

Output-4