Skip to content

problem20.md

Latest commit

 

History

History
13 lines (10 loc) · 514 Bytes

problem20.md

File metadata and controls

13 lines (10 loc) · 514 Bytes

Problem 20: The Rod Cutter (Rod Cutting Problem)

Problem Statement

Given a rod of length n and a table of prices price[i] for rod lengths i = 1, 2, ..., n, determine the maximum revenue obtainable by cutting up the rod and selling the pieces.

Input Format

  • An integer n (length of the rod).
  • An array price of length n.

Example

Input: n = 8, price = [1, 5, 8, 9, 10, 17, 17, 20]
Output: 22
Explanation: Cut the rod into pieces of length 2 and 6 (revenue = 5 + 17 = 22).