dynamic_programming.rod_cutting

This module provides two implementations for the rod-cutting problem: 1. A naive recursive implementation which has an exponential runtime 2. Two dynamic programming implementations which have quadratic runtime

The rod-cutting problem is the problem of finding the maximum possible revenue obtainable from a rod of length n given a list of prices for each integral piece of the rod. The maximum revenue can thus be obtained by cutting the rod and selling the pieces separately or not cutting it at all if the price of it is the maximum obtainable.

Functions

_enforce_args(n, prices)

Basic checks on the arguments to the rod-cutting algorithms

_top_down_cut_rod_recursive(n, prices, max_rev)

Constructs a top-down dynamic programming solution for the rod-cutting problem

bottom_up_cut_rod(n, prices)

Constructs a bottom-up dynamic programming solution for the rod-cutting problem

main()

naive_cut_rod_recursive(n, prices)

Solves the rod-cutting problem via naively without using the benefit of dynamic

top_down_cut_rod(n, prices)

Constructs a top-down dynamic programming solution for the rod-cutting

Module Contents

dynamic_programming.rod_cutting._enforce_args(n: int, prices: list)

Basic checks on the arguments to the rod-cutting algorithms

n: int, the length of the rod prices: list, the price list for each piece of rod.

Throws ValueError:

if n is negative or there are fewer items in the price list than the length of the rod

dynamic_programming.rod_cutting._top_down_cut_rod_recursive(n: int, prices: list, max_rev: list)

Constructs a top-down dynamic programming solution for the rod-cutting problem via memoization.

Runtime: O(n^2)

Arguments

n: int, the length of the rod prices: list, the prices for each piece of rod. p[i-i] is the price for a rod of length i max_rev: list, the computed maximum revenue for a piece of rod. max_rev[i] is the maximum revenue obtainable for a rod of length i

Returns

The maximum revenue obtainable for a rod of length n given the list of prices for each piece.

dynamic_programming.rod_cutting.bottom_up_cut_rod(n: int, prices: list)

Constructs a bottom-up dynamic programming solution for the rod-cutting problem

Runtime: O(n^2)

Arguments

n: int, the maximum length of the rod. prices: list, the prices for each piece of rod. p[i-i] is the price for a rod of length i

Returns

The maximum revenue obtainable from cutting a rod of length n given the prices for each piece of rod p.

Examples

>>> bottom_up_cut_rod(4, [1, 5, 8, 9])
10
>>> bottom_up_cut_rod(10, [1, 5, 8, 9, 10, 17, 17, 20, 24, 30])
30
dynamic_programming.rod_cutting.main()
dynamic_programming.rod_cutting.naive_cut_rod_recursive(n: int, prices: list)

Solves the rod-cutting problem via naively without using the benefit of dynamic programming. The results is the same sub-problems are solved several times leading to an exponential runtime

Runtime: O(2^n)

Arguments

n: int, the length of the rod prices: list, the prices for each piece of rod. p[i-i] is the price for a rod of length i

Returns

The maximum revenue obtainable for a rod of length n given the list of prices for each piece.

Examples

>>> naive_cut_rod_recursive(4, [1, 5, 8, 9])
10
>>> naive_cut_rod_recursive(10, [1, 5, 8, 9, 10, 17, 17, 20, 24, 30])
30
dynamic_programming.rod_cutting.top_down_cut_rod(n: int, prices: list)

Constructs a top-down dynamic programming solution for the rod-cutting problem via memoization. This function serves as a wrapper for _top_down_cut_rod_recursive

Runtime: O(n^2)

Arguments

n: int, the length of the rod prices: list, the prices for each piece of rod. p[i-i] is the price for a rod of length i

Note

For convenience and because Python’s lists using 0-indexing, length(max_rev) = n + 1, to accommodate for the revenue obtainable from a rod of length 0.

Returns

The maximum revenue obtainable for a rod of length n given the list of prices for each piece.

Examples

>>> top_down_cut_rod(4, [1, 5, 8, 9])
10
>>> top_down_cut_rod(10, [1, 5, 8, 9, 10, 17, 17, 20, 24, 30])
30