Example: Rod Cutting - rFronteddu/general_wiki GitHub Wiki

len i	1	2	3	4	5	6	7	8	9	10
price $p_i$	1	5	8	9	10	17	17	20	24	30

i	0	1	2	3	4	5	6	7	8	9	10
r[i]	0	1	5	8	10	13	17	18	22	25	30
s[i]	/	1	2	3	2	2	6	1	2	3	10

• We are given a rod of length n and a price table $p_i$ for each len i=1..n and we are tasked to find the maximum revenue $r_n$.

• We observe that an optimal solution cuts the rod in k ($1 \leq k \leq n$) pieces decomposing the rod n = $i_1 + i_2 + ... + i_k$ in pieces of length $i_1, i_2, ..., i_k$ yielding total revenue $r_n$ = $p_{i_1}+p_{i_2}+...+p_{i_k}$.

• From this we can reframe finding the total revenue $r_n$ for $n \geq 1$ in terms of optimal smaller cuts.

• $r_n$ = max ( $p_n, p_1 + r_{n-1}, p_2 + r_{n-2},...,p_{n-1} + r_{1}$ )

  • The first term corresponds to making no cut obtaining a revenue $p_n$
  • The other terms correspond to the revenue obtained by making a first cut of length i, and then using the optimal revenue of what is left
  • Each problem is a smaller problem of size n-i for each i=1..n, we do not know i but we can search for it)

• The problems becomes finding $r_n$=max ($p_i + r_{n-i}$) for $1 \leq i \leq n$

• We use two array, one to keep track of $r_n$ and one to keep track of i

RC(p, n)
    let r[0..n] and s[1..n] be two arrays
    r[0] = 0
    for i = 1 to n
        r[i] = -Inf
        for j = 1 to i
            q = p[j] + r[i-j]
            if r[i] < q
                r[i] = q
                s[i] = j
    return r and s

PrintRC(s, n)
    while n > 0
        print(s[n])
        n = n - s[n]