From 59c024c77df970c52956142bce280f26876bc022 Mon Sep 17 00:00:00 2001 From: mo khan Date: Sun, 21 Nov 2021 16:46:48 -0700 Subject: add recursive solution for rod cutting --- exercises/15.1/rod_cutting.rb | 25 +++++++++++++++++++++++++ 1 file changed, 25 insertions(+) create mode 100644 exercises/15.1/rod_cutting.rb (limited to 'exercises') diff --git a/exercises/15.1/rod_cutting.rb b/exercises/15.1/rod_cutting.rb new file mode 100644 index 0000000..ce9f058 --- /dev/null +++ b/exercises/15.1/rod_cutting.rb @@ -0,0 +1,25 @@ +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 + +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 +end -- cgit v1.2.3