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
|
package main
import (
"testing"
)
func max(x, y int) int {
if x > y {
return x
}
return y
}
func cutRod(p []int, n int) int {
if n == 0 {
return 0
}
q := -1
for i := 1; i <= n; i++ {
q = max(q, p[i]+cutRod(p, n-i))
}
return q
}
func memoizedCutRodAux(p []int, n int, r []int) int {
if r[n] >= 0 {
return r[n]
}
if n == 0 {
return 0
}
q := -1
for i := 1; i <= n; i++ {
q = max(q, p[i]+memoizedCutRodAux(p, n-i, r))
}
r[n] = q
return q
}
func memoizedCutRod(p []int, n int) int {
r := []int{}
for i := 0; i <= n; i++ {
r = append(r, -1)
}
return memoizedCutRodAux(p, n, r)
}
func bottomUpCutRod(p []int, n int) int {
if n == 0 {
return 0
}
r := []int{0}
for i := 1; i <= n; i++ {
r = append(r, -1)
}
for j := 1; j <= n; j++ {
q := -1
for i := 1; i <= j; i++ {
q = max(q, p[i]+r[j-i])
}
r[j] = q
}
return r[n]
}
func TestRodCutting(t *testing.T) {
r := []int{0, 1, 5, 8, 10, 13, 17, 18, 22, 25, 30}
p := []int{0, 1, 5, 8, 9, 10, 17, 17, 20, 24, 30}
t.Run("with recursive approach", func(t *testing.T) {
for n := 0; n < len(p); n++ {
expected := r[n]
actual := cutRod(p, n)
if expected != actual {
t.Errorf("%d: expected %d, actual %d", n, expected, actual)
}
}
})
t.Run("with top down dynamic programming approach", func(t *testing.T) {
for n := 0; n < len(p); n++ {
expected := r[n]
actual := memoizedCutRod(p, n)
if expected != actual {
t.Errorf("%d: expected %d, actual %d", n, expected, actual)
}
}
})
t.Run("with bottom up dynamic programming approach", func(t *testing.T) {
for n := 0; n < len(p); n++ {
expected := r[n]
actual := bottomUpCutRod(p, n)
if expected != actual {
t.Errorf("%d: expected %d, actual %d", n, expected, actual)
}
}
})
}
|
