Go-Algorithm/dynamic/rodcutting.go at master · hanfengyizu/Go-Algorithm · GitHub

Repository navigation

// Solution to Rod cutting problem

// https://en.wikipedia.org/wiki/Cutting_stock_problem

// http://www.geeksforgeeks.org/dynamic-programming-set-13-cutting-a-rod/

package dynamic

// CutRodRec solve the problem recursively: initial approach

func CutRodRec(price []int, length int) int {

if length == 0 {

return 0

}

q := -1

for i := 1; i <= length; i++ {

q = Max(q, price[i]+CutRodRec(price, length-i))

}

return q

}

// CutRodDp solve the same problem using dynamic programming

func CutRodDp(price []int, length int) int {

r := make([]int, length+1) // a.k.a the memoization array

r[0] = 0 // cost of 0 length rod is 0

for j := 1; j <= length; j++ { // for each length (subproblem)

q := -1

for i := 1; i <= j; i++ {

q = Max(q, price[i]+r[j-i]) // avoiding recursive call

}

r[j] = q

}

return r[length]

}

func main() {

length := 10

price := []int{0, 1, 5, 8, 9, 17, 17, 17, 20, 24, 30}

// price := []int{0, 10, 5, 8, 9, 17, 17, 17, 20, 24, 30}

// fmt.Print(price[5]+price[length-5], "\n")

fmt.Print(cutRodRec(price, length), "\n")

fmt.Print(cutRodDp(price, length), "\n")

}