rod-cutting Algorithm
The rod-cutting algorithm is a dynamic programming technique used for solving optimization problems, specifically those involving the division of a given resource. The classic problem that this algorithm addresses involves cutting a rod of a certain length into smaller pieces to maximize the total profit obtained by selling the individual pieces. Each piece has a different value associated with it, depending on its length, and the goal is to determine the best way to cut the rod to maximize the total value. The rod-cutting algorithm is widely used in various industries, including steel, paper, and textile manufacturing, where the efficient allocation of resources is essential for maximizing revenue.
The rod-cutting algorithm uses a bottom-up approach, solving smaller subproblems first and gradually building up to the final solution. The algorithm starts by considering the optimal way to cut a rod of length 1, then length 2, and so on, until the optimal solution for the entire rod length is obtained. This is achieved by using a memoization table to store the optimal solutions for each subproblem, thus avoiding redundant calculations and significantly reducing the overall computational complexity. The rod-cutting algorithm is highly efficient and versatile, making it a popular choice for solving a wide range of optimization problems in computer science, operations research, and various engineering domains.
// 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 dpRodCutting
// package main
import "fmt"
func max(a, b int) int {
if a > b {
return a
} else {
return b
}
}
// 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
}
// 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")
}
*/
