exercises/15.1/rod_cutting.py


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

import unittest

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

class TestRodCutting(unittest.TestCase):
    def setUp(self):
        self.p = [0, 1, 5, 8, 9, 10, 17, 17, 20, 24, 30]
        self.r = [0, 1, 5, 8, 10, 13, 17, 18, 22, 25, 30]

    def test_recursive(self):
        for n in range(10):
            self.assertEqual(self.r[n], cutRod(self.p, n))

if __name__ == '__main__':
    unittest.main()