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
|
require "minitest/autorun"
def cut_rod(p, n)
return 0 if n == 0
q = -1
1.upto(n) do |i|
q = [q, p[i] + cut_rod(p, n - i)].max
end
q
end
def memoized_cut_rod_aux(p, n, r)
return r[n] if r[n] >= 0
return 0 if n == 0
q = -1
1.upto(n) do |i|
q = [q, p[i] + memoized_cut_rod_aux(p, n-i, r)].max
end
r[n] = q
q
end
def memoized_cut_rod(p, n)
r = []
0.upto(n) do |i|
r[i] = -1
end
memoized_cut_rod_aux(p, n, r)
end
class RodCuttingTest < Minitest::Test
def setup
@prices = [ 0, 1, 5, 8, 9, 10, 17, 17, 20, 24, 30]
@max_revenue = [ 0, 1, 5, 8, 10, 13, 17, 18, 22, 25, 30]
@max_cuts = [ 0, 1, 2, 3, 2, 2, 6, 1, 2, 3, 10]
end
def test_recursive_rod_cutting
0.upto(10) do |n|
assert_equal @max_revenue[n], cut_rod(@prices, n), "n: #{n}"
end
end
def test_top_down_dynamic_programming_approach
0.upto(10) do |n|
assert_equal @max_revenue[n], memoized_cut_rod(@prices, n), "n: #{n}"
end
end
end
|
