The Rod Cutting problem

Question

Given a rod of length n inches and a list of prices that contains prices of all pieces of size smaller than n. Determine the maximum value obtainable by cutting up the rod and selling the pieces. For example, if length of the rod is 8 and the values of different pieces are given as following, then the maximum obtainable value is 22 (by cutting in two pieces of lengths 2 and 6)

length   | 1   2   3   4   5   6   7   8  
-------------------------------------------
price    | 1   5   8   9  10  17  17  20

And if the prices are as following, then the maximum obtainable value is 24 (by cutting in eight pieces of length 1)

length   | 1   2   3   4   5   6   7   8  
--------------------------------------------
price    | 3   5   8   9  10  17  17  20

The input will be given in this form: The prices will be in ascending order, index starting at 1 to n separated by a space.

{price of length 1} {price of length 2}.... {price of length N}

The output should be the maximum Obtainable Value

{maxVal}

a Non-Golfed solution to this, in Python is:

INT_MIN = -32767
def cutRod(price, n): 
    val = [0 for x in range(n+1)] 
    val[0] = 0
    for i in range(1, n+1): 
        max_val = INT_MIN 
        for j in range(i): 
             max_val = max(max_val, price[j] + val[i-j-1]) 
        val[i] = max_val 
  
    return val[n] 
  
arr = [1,2,3,4,5,6,7,8,9,10] 
size = len(arr) 
print(cutRod(arr, size))

Test cases:

|                                      Input                                     | Output |
|:------------------------------------------------------------------------------:|:------:|
|                              `1 5 8 9 10 17 17 20`                             |  `22`  |
|                                `1 3 2 5 6 7 4 8`                               |  `12`  |
|                     `5 6 3 2 4 6 8 7 3 4 6 2 12 4 5 7 4 3`                     |  `90`  |
| `23 2 3 45 34 23 3143 13 13 213 1321 3123 12 312 312 31 3 213 432 41 3 123 43` | `9475` |

Answer 1

Jelly, 7 bytes

LŒṗịµ§Ṁ
L        length
 Œṗ      integer partitions
   ị     index
     §Ṁ  sum each and take the maximum

My first jelly answer, so there can probably be improvements made.

Try it online!

Answer 2

JavaScript (Node.js), 57 bytes

a=>a.map((v,i)=>a[i]=w=a.map(u=>v=(u+=a[--i])>v?u:v)|v)|w

Try it online!

As the question is a knapsack problem. Let \$ val\left[i\right] \$ be the price of segment of length \$i\$. We have:

$$ dp\left[0\right] = 0$$ $$ dp\left[i\right] = \max_{j=1..i} \left\{ val\left[j\right] + dp\left[i-j\right] \right\} $$

And \$dp\left[len\right]\$ is the answer.

To golf more bytes, we slightly modify the transition equation into $$ dp\left[i\right] = \max\left\{val\left[i\right], \max_{j=1..i-1} \left\{ dp\left[j\right] + dp\left[i-j\right] \right\} \right\} $$

We use \$a\$ for both \$val\$ and \$dp\$ during iteration. When try to calculate \$a\left[i\right]\$, all values \$a\left[0..i-1\right]\$ equals to \$dp\$ and all other values equals to \$val\$. Also, our array is 0-indexed instead of 1-indexed. So we modify the equation into

$$ a\left[i\right] = \max\left\{a\left[i\right], \max_{j=0..i-1} \left\{ a\left[j\right] + a\left[i-j-1\right] \right\} \right\} $$

Use the feature that when access values out of array range, undefined is returned. And mathematics operation on undefined results NaN. NaN>v will also be false. We can ignore \$j=0..i-1\$ part from \$\max\$. And the code is shown above.

Ungolfed C program as reference:

int f(int* a) {
  int i, j, val;
  // before loop: a[i] = price of length (i+1) segement
  // after loop: a[i] = max sum price of cutted length (i+1) segment
  for (i = 0; a[i]; i++) {
    // before loop j
    // a[i] = price of length (i+1) segment
    //      = price if do not cut the segment
    for (j = 0; j < i; j++) {
      // price when cut the segment into two parts with length (j+1), (i-j)
      val = a[j] + a[i - j - 1];
      // we prefer higher price if we can
      if (a[i] < val) {
        a[i] = val;
      }
    } // j
  } // i
  return a[i - 1];
}

Try it online!

Above C code may golf to 81 bytes, but still longer than JavaScript implementation. :(

---

• -5 bytes thanks to Arnauld

Answer 3

JavaScript (ES6), 78 bytes

Saved 1 byte thanks to @Davide

a=>(m=F=(n,i=0,s=0)=>n?i>n||F(n+~i,i,s+a[i])|F(n,i+1,s):m=s<m?m:s)(a.length)&m

Try it online!

Commented

a => (              // a[] = input array
  m =               // initialize m to a non-numeric value
  F = (             // F is a recursive function taking:
    n,              //   n = integer to be partitioned
    i = 0,          //   i = integer to be subtracted from n (-1)
    s = 0           //   s = price sum
  ) =>              //
    n ?             // if n is not equal to 0:
      i > n         //   abort if i is greater than n
      ||            //   otherwise:
        F(          //     first recursive call with:
          n + ~i,   //       n - i - 1
          i,        //       i unchanged
          s + a[i]  //       s + i-th price
        ) |         //
        F(          //     second recursive call with:
          n,        //       n unchanged
          i + 1,    //       i + 1
          s         //       s unchanged
        )           //
    :               // else:
      m = s < m ? m //   update m to max(m, s)
                : s //
)(a.length)         // initial call to F with n = length of a[]
& m                 // return m

Answer 4

C (gcc), 98 89 bytes

-9 bytes thanks to ceilingcat

m;*n;l;g(N,L)int*N;{n=N;l=L;f(0,m=0);}f(t,s,i){m<t?m=t:0;for(i=0;++i<l-s;f(t+n[i],s+i));}

Try it online!

Explanation

That's the explanation of a previous illegal version, but not so much has changed, so the explanation is still valid.

The function f() call itself recursively and into a loop, so that for each index of the loop it starts a whole new loop, and for each index of this other loop it launches a whole new loop and so on.

Each branch stops when the sum of the lengths of the pieces of that particular branch reaches the length of the rod.

Every time, before to enter a new branch-generating loop, the current maximum value possible is compared with that of the branch and eventually updated to a greater value.

m;             // variable used to store the maximum value possible
f(            // this is a recursive function creating all the possible combinations of the pieces
n,            // it takes: an array of integers
l,             // the length of the array
t,            // the total price of the current branch
s)             // the sum of the inches virtually sold till now
int*n;{                            
    m<t?m=t:0;    // if the maximum value is less than the total of a branch, update it
    for(int i=0;  // `i` represents the inches of a particular piece
    ++i<l-s;      // untill `i` is less than the maximum length minus the current sum of the inches
      f(         // f() calls itself with:
      n,         // the same array
      l,          // the same length
      t+n[i],     // the current total price plus the price of this one more piece
      s+i)        // the current sum of the inches plus the length of this one more piece
    );            // end of for() loop
}                // end of function

Ported to JavaScript

Answer 5

Wolfram Language (Mathematica), 33 bytes

Max[Range@#~FrobeniusSolve~#.#2]&

Try it online!

Input the length and list of prices.

Answer 6

Python 3.8 (pre-release), 51 bytes

f=lambda l,n:n and max(x+f(l,n:=n-1)for x in l[:n])

Try it online!

Same length:

51 bytes

f=lambda l,n:max([0]+[x+f(l,n:=n-1)for x in l[:n]])

Try it online!

Answer 7

JavaScript (Node.js), 82 79 bytes

(n,m=0)=>(g=(t,s,i=0)=>{m<t?m=t:0;while(i<n.length-s)g(t+n[i],s-~i++);})(0,0)|m

Try it online!

That's my first JavaScript answer!!

Made translating my C answer. The algorithm is the same (you can read the explanation from there if interested).

Answer 8

Wenyan Language, 2178 bytes

I know what you're going to say -- WHAT ON EARTH IS THIS?!

吾有一術名之曰「獲取」欲行是術必先得一物曰「對象」一物曰「域」乃行是術曰乃得對象[域]是謂「獲取」之術也吾有一術名之曰「賦值」欲行是術必先得一物曰「對象」一物曰「域」一物曰「值」乃行是術曰乃得對象[域]=值是謂「賦值」之術也減零以三萬二千七百六十七名之曰「極小」吾有一術名之曰「分桿」欲行是術必先得一物曰「物價」一物曰「桿數」乃行是術曰吾有一列名之曰「遞歸」昔之「索引」者今零是矣恆為是吾有一爻名之曰「甲丙」若「索引」不大於「桿數」者昔之「甲丙」者今陽是矣云云若「甲丙」等於零者乃止云云充「遞歸」以零加「索引」以一昔之「索引」者今其是矣云云昔之「索引」者今一是矣恆為是加「桿數」以一吾有一爻名之曰「甲申」若「索引」小於其者昔之「甲申」者今陽是矣云云若「甲申」等於零者乃止云云吾有一物曰「極小」名之曰「最大」昔之「索引其二」者今零是矣恆為是吾有一爻名之曰「亥卯」若「索引其二」小於「索引」者昔之「亥卯」者今陽是矣云云若「亥卯」等於零者乃止云云吾有一術名之曰「丁戊」欲行是術必先得一物曰「a」一物曰「b」乃行是術曰乃得Math.max(a,b)是謂「丁戊」之術也施「獲取」於「物價」於「索引其二」名之曰「子甲」減「索引」以「索引其二」夫「遞歸」之其加「子甲」以其名之曰「午申」施「丁戊」於「最大」於「午申」昔之「最大」者今其是矣加「索引其二」以一昔之「索引其二」者今其是矣云云施「賦值」於「遞歸」於「索引」於「最大」噫加「索引」以一昔之「索引」者今其是矣云云施「獲取」於「遞歸」於「桿數」。名之曰「支子」乃得 「支子」是謂「分桿」之術也噫吾有一列名之曰「桿長」吾有一數名之曰「桿數」夫「桿長」之長昔之「桿數」者今其是矣施「分桿」於「桿長」於「桿數」名之曰「卯地」吾有一物曰「卯地」書之

Expect an input at char 678:

...
吾有一列名之曰「桿長」(INPUT GOES HERE!)吾有一數
...

Using the format:

充「桿長」以(some number)以(some number)以(some number)以......

Well I know it's difficult for those who don't understand Chinese. Fortunately the language compiles into equivalent JavaScript. I'll show it below for you to understand:

var 獲取 = () => 0
獲取 = function(對象) {
  return function(域) {
    return 對象[域]
  }
}
var 賦值 = () => 0
賦值 = function(對象) {
  return function(域) {
    return function(值) {
      return (對象[域] = 值)
    }
  }
}
// Notice that functions above are only for convenience, because all function calls in this language is curry.

var 極小 = 0 - 32767

// The main function
var 分桿 = () => 0
分桿 = function(物價) {
  return function(桿數) {
    // The above two lines is to make the function a curry.
    var 遞歸 = []
    索引 = 0
    while (true) {
      // In this language we only have while-loops, but we can use 'if' and 'break' to control it.
      var 甲丙 = false
      if (索引 <= 杆數) {
        甲丙 = true
      }
      if (甲丙 == 0) {
        break
      }
      遞歸.push(0)
      索引 = 索引 + 1
    }
    索引 = 1
    while (true) {
      var 甲申 = false
      if (索引 < 杆數 + 1) {
        甲申 = true
      }
      if (甲申 == 0) {
        break
      }
      var 最大 = 極小
      索引其二 = 0
      while (true) {
        var 亥卯 = false
        if (索引其二 < 索引) {
          亥卯 = true
        }
        if (亥卯 == 0) {
          break
        }
        var 丁戊 = () => 0
        丁戊 = function(a) {
          return function(b) {
            return Math.max(a, b)
          }
        }
        var 子甲 = 獲取(物價)(索引其二)
        var _ans5 = 索引 - 索引其二
        var _ans6 = 遞歸[_ans5 - 1]
        var _ans7 = 子甲 + _ans6
        var 午申 = _ans7
        最大 = 丁戊(最大)(午申)
        索引其二 = 索引其二 + 1
      }
      var _ans10 = 賦值(遞歸)(索引)(最大)
      索引 = 索引 + 1
    }
    var 支子 = 獲取(遞歸)(杆數)
    return 支子
  }
}
var 桿長 = []
// There should be some input...
杆數 = 桿長.length
var 卯地 = 分桿()
console.log(卯地) // Program complete

Answer 9

05AB1E, 7 bytes

gÅœ<èOà

Try it online or verify all test cases.

Explanation:

g        # Get the length of the (implicit) input-list
 Ŝ      # Get all lists of positive integers that sum to this length
   <     # Decrease each by 1 to make it a 0-based index
    è    # Index those into the (implicit) input-list
     O   # Sum each inner list
      à  # Pop and push the maximum
         # (after which it is output implicitly as result)

Try it online with step-by-step output.

Answer 10

Charcoal, 19 bytes

ＦＡ⊞υ⌈⊞ＯＥ⮌υ⁺κ§υλιＩ⊟υ

Try it online! Link is to verbose version of code. Explanation: Based on @tsh's approach.

ＦＡ

Loop over each input element.

⊞υ⌈⊞ＯＥ⮌υ⁺κ§υλι

The value of each length is the maximum of the current input element and the array sum of the array of values so far with its reverse. This is pushed to the array of values.

Ｉ⊟υ

Output the last value.

Answer 11

Python 3, 103 bytes

lambda p,n:max(map(sum,d(p,n)))
d=lambda p,n:[[p[n-1]]]+[m+[p[i]]for i in range(n-1)for m in d(p,n+~i)]

Try it online!

Inputs the prices as a list of integers along with the length of the rod.
Returns the maximum price you can get.

Uses a variation of the integer partition function I wrote for my Landau logarithm answer.

Answer 12

Pyth, 13 bytes

eSmsm@Qtkd./l

Try it online!

The obvious approach: try all integer partitions, compute their value, and take the maximum. I spent a while trying to use the M or L builtins, but they didn't end up being shorter.

Answer 13

Julia 1.0, ⁴⁷ 36 bytes

port of xnor's answer

n*l=max(0,(1:n.|>x->l[x]+(n-x)l)...)

Try it online!

Julia 0.4, 42 bytes

or with Julia 1.0+ and Combinatorics.jl

f(p,n)=maximum(x->sum(p[x]),partitions(n))

Try it online!

Answer 14

Scala, 98 bytes

Port of @tsh's Javascript answer in Scala.

---

Golfed version. Try it online!

a=>{var i,j,v=0;while(a(i)!=0){j=0;while(j<i){v=a(j)+a(i-j-1);if(a(i)<v)a(i)=v;j+=1};i+=1};a(i-1)}

Ungolfed version. Try it online!

object Main {
  def f(a: Array[Int]): Int = {
    var i = 0
    var j = 0
    var val_ = 0

    while (a(i) != 0) {
      j = 0
      while (j < i) {
        val_ = a(j) + a(i - j - 1)
        if (a(i) < val_) {
          a(i) = val_
        }
        j += 1
      }
      i += 1
    }
    a(i - 1)
  }

  def main(args: Array[String]): Unit = {
    val n = Array(
      Array(1, 5, 8, 9, 10, 17, 17, 20, 0),
      Array(1, 3, 2, 5, 6, 7, 4, 8, 0),
      Array(5, 6, 3, 2, 4, 6, 8, 7, 3, 4, 6, 2, 12, 4, 5, 7, 4, 3, 0),
      Array(23, 2, 3, 45, 34, 23, 3143, 13, 13, 213, 1321, 3123, 12, 312, 312, 31, 3, 213, 432, 41, 3, 123, 43, 0)
    )

    for (i <- n.indices) {
      println(f(n(i)))
    }
  }
}