FilesExpand file tree

master

/

rod_cutting.py

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

200 lines (153 loc) · 6.04 KB

master

/

rod_cutting.py

Copy path

Top

File metadata and controls

• Code
• Blame

200 lines (153 loc) · 6.04 KB

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

58

59

60

61

62

63

64

65

66

67

68

69

70

71

72

73

74

75

76

77

78

79

80

81

82

83

84

85

86

87

88

89

90

91

92

93

94

95

96

97

98

99

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

170

171

172

173

174

175

176

177

178

179

180

181

182

183

184

185

186

187

188

189

190

191

192

193

194

195

196

197

198

199

200

"""

This module provides two implementations for the rod-cutting problem:

1. A naive recursive implementation which has an exponential runtime

2. Two dynamic programming implementations which have quadratic runtime

The rod-cutting problem is the problem of finding the maximum possible revenue

obtainable from a rod of length ``n`` given a list of prices for each integral piece

of the rod. The maximum revenue can thus be obtained by cutting the rod and selling the

pieces separately or not cutting it at all if the price of it is the maximum obtainable.

"""

def naive_cut_rod_recursive(n: int, prices: list):

"""

Solves the rod-cutting problem via naively without using the benefit of dynamic programming.

The results is the same sub-problems are solved several times leading to an exponential runtime

Runtime: O(2^n)

Arguments

-------

n: int, the length of the rod

prices: list, the prices for each piece of rod. ``p[i-i]`` is the

price for a rod of length ``i``

Returns

-------

The maximum revenue obtainable for a rod of length n given the list of prices for each piece.

Examples

--------

>>> naive_cut_rod_recursive(4, [1, 5, 8, 9])

10

>>> naive_cut_rod_recursive(10, [1, 5, 8, 9, 10, 17, 17, 20, 24, 30])

30

"""

_enforce_args(n, prices)

if n == 0:

return 0

max_revue = float("-inf")

for i in range(1, n + 1):

max_revue = max(

max_revue, prices[i - 1] + naive_cut_rod_recursive(n - i, prices)

)

return max_revue

def top_down_cut_rod(n: int, prices: list):

"""

Constructs a top-down dynamic programming solution for the rod-cutting problem

via memoization. This function serves as a wrapper for _top_down_cut_rod_recursive

Runtime: O(n^2)

Arguments

--------

n: int, the length of the rod

prices: list, the prices for each piece of rod. ``p[i-i]`` is the

price for a rod of length ``i``

Note

----

For convenience and because Python's lists using 0-indexing, length(max_rev) = n + 1,

to accommodate for the revenue obtainable from a rod of length 0.

Returns

-------

The maximum revenue obtainable for a rod of length n given the list of prices for each piece.

Examples

-------

>>> top_down_cut_rod(4, [1, 5, 8, 9])

10

>>> top_down_cut_rod(10, [1, 5, 8, 9, 10, 17, 17, 20, 24, 30])

30

"""

_enforce_args(n, prices)

max_rev = [float("-inf") for _ in range(n + 1)]

return _top_down_cut_rod_recursive(n, prices, max_rev)

def _top_down_cut_rod_recursive(n: int, prices: list, max_rev: list):

"""

Constructs a top-down dynamic programming solution for the rod-cutting problem

via memoization.

Runtime: O(n^2)

Arguments

--------

n: int, the length of the rod

prices: list, the prices for each piece of rod. ``p[i-i]`` is the

price for a rod of length ``i``

max_rev: list, the computed maximum revenue for a piece of rod.

``max_rev[i]`` is the maximum revenue obtainable for a rod of length ``i``

Returns

-------

The maximum revenue obtainable for a rod of length n given the list of prices for each piece.

"""

if max_rev[n] >= 0:

return max_rev[n]

elif n == 0:

return 0

else:

max_revenue = float("-inf")

for i in range(1, n + 1):

max_revenue = max(

max_revenue,

prices[i - 1] + _top_down_cut_rod_recursive(n - i, prices, max_rev),

)

max_rev[n] = max_revenue

return max_rev[n]

def bottom_up_cut_rod(n: int, prices: list):

"""

Constructs a bottom-up dynamic programming solution for the rod-cutting problem

Runtime: O(n^2)

Arguments

----------

n: int, the maximum length of the rod.

prices: list, the prices for each piece of rod. ``p[i-i]`` is the

price for a rod of length ``i``

Returns

-------

The maximum revenue obtainable from cutting a rod of length n given

the prices for each piece of rod p.

Examples

-------

>>> bottom_up_cut_rod(4, [1, 5, 8, 9])

10

>>> bottom_up_cut_rod(10, [1, 5, 8, 9, 10, 17, 17, 20, 24, 30])

30

"""

_enforce_args(n, prices)

# length(max_rev) = n + 1, to accommodate for the revenue obtainable from a rod of length 0.

max_rev = [float("-inf") for _ in range(n + 1)]

max_rev[0] = 0

for i in range(1, n + 1):

max_revenue_i = max_rev[i]

for j in range(1, i + 1):

max_revenue_i = max(max_revenue_i, prices[j - 1] + max_rev[i - j])

max_rev[i] = max_revenue_i

return max_rev[n]

def _enforce_args(n: int, prices: list):

"""

Basic checks on the arguments to the rod-cutting algorithms

n: int, the length of the rod

prices: list, the price list for each piece of rod.

Throws ValueError:

if n is negative or there are fewer items in the price list than the length of the rod

"""

if n < 0:

raise ValueError(f"n must be greater than or equal to 0. Got n = {n}")

if n > len(prices):

raise ValueError(

f"Each integral piece of rod must have a corresponding "

f"price. Got n = {n} but length of prices = {len(prices)}"

)

def main():

prices = [6, 10, 12, 15, 20, 23]

n = len(prices)

# the best revenue comes from cutting the rod into 6 pieces, each

# of length 1 resulting in a revenue of 6 * 6 = 36.

expected_max_revenue = 36

max_rev_top_down = top_down_cut_rod(n, prices)

max_rev_bottom_up = bottom_up_cut_rod(n, prices)

max_rev_naive = naive_cut_rod_recursive(n, prices)

assert expected_max_revenue == max_rev_top_down

assert max_rev_top_down == max_rev_bottom_up

assert max_rev_bottom_up == max_rev_naive

if __name__ == "__main__":

main()