Cutting yarn into integer-length pieces to maximize profit based on known prices for each length

Question

My classmates and I were working on a problem on our introduction to algorithms homework, but we are having a lot of trouble wrapping our heads around it. Below is the problem:

We are given a string of yarn of length $n$ meters, and our goal is to cut this yarn into integer-length pieces. For every integer $1..n$ we know the selling price of a piece of yarn of that length. We call the selling price of a string of yarn of length $i$ by $p_i ≥ 0$. We must give an algorithm to compute the maximum amount of money that we could make by cutting the string into integer-length pieces. Our algorithm must run in $O(n^2)$.

So we know that this type of problem can be solved using a dynamic programming approach, but we're having trouble coming up with a recurrence relation. We think that we should start with an array $L$ such that $L[i]$ denotes the maximum amount of money given with a certain amount of cuts, but we're uncertain about how exactly we should represent this and where to go on from here.

Thanks a lot in advance!

Answer 1

This answer isn't really helpful for your assignment and isn't framed in terms of dynamic programming. It's just about solving the problem fast.

This problem can be solved in $O(n \lg^2 n)$ time by using iterative max-convolution on the prices.

Max-convolution takes an array $a$ and tells you $\max_j^d (a_j + a_{d-j})$ for each starting offset $d$. By being clever you can do it in $O(n \lg n)$ time instead of $O(n^2)$, kinda reminiscent of the convolution theorem.

edit: but see @Kaban-5's important caveat in the comments, about this algorithm depending on random inputs instead of random choices!

The key thing to realize is that, if the price for a piece of length $d$ is less than the price of a piece of length $d-j$ plus a piece of length $j$, then the effective price for a piece of length $d$ should increase to the sum of those two prices. And if we keep looking for these pricing inefficiencies and fixing them, we'll converge on the true optimal selling price for each length.

A single max-convolution will replace every price with the maximum you can get by splitting a piece into up to two pieces and selling all the pieces. A second max-convolution will be searching through all splits into up to 4 pieces. The third goes up to 8. And so forth until we hit up-to-$n$ after the $\lg n$'th max-convolution.

Here's the algorithm:

def bestSplitPrice(prices):
    """
    Assuming you have a piece of yarn of length len(prices)+1, find
    the best price you can get by cutting it and selling the pieces
    at the given prices-per-length.
    """
    prices = [0] + prices #A zero-length piece costs nothing
    for i in range(ceil(lg2(prices))):
        prices = max_convolve(prices, prices)[:len(prices)]
    return prices[-1]

And here's an example:

prices = {1:1$, 2:3$, 3:3$, 4:4$, 5:5$, 6:5$, 7:7$}
# array-ify, including 0-length price
prices = [0, 1, 3, 3, 4, 5, 5, 7]
# max-convolve lg2(8) = 3 times
prices = [0, 1, 3, 4, 6, 6, 7, 8]
prices = [0, 1, 3, 4, 6, 7, 9, 10]
prices = [0, 1, 3, 4, 6, 7, 9, 10]

The best piece-price for length-7 is 10$

Here's how the max-convolutions play out if only the 1$ piece is given a price:

prices = [0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
prices = [0, 1, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
prices = [0, 1, 2, 3, 4, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3]
prices = [0, 1, 2, 3, 4, 5, 6, 7, 8, 7, 7, 7, 7, 7, 7, 7]
prices = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9,10,11,12,13,14,15]

Notes:

• I suspect this can be cut to $O(n \lg n)$ by having the max-convolutions double-hitting exponentially larger and larger sections of the array.

Answer 2

Your problem is a classic one (a variant of the knapsack problem). Maybe is more clear to you, if you see explicitly the overlapping into subproblems, something necessary to apply the dynamic programing paradigm, after then, is natural come up with the recursion relation.

For example, when you have the rod of length $n$, you can cut it in so many ways, like cut in $1$ or $2$, thats it, ending with a rod of lengths $[1$ and $n-1]$ or $[2$ and $n-2]$, respectively. In each case, you find the maximum profit and the compare with the other options, as we expect.

$$l(n):=\text{ maximun profit of cutting the rod of length $n$ in all possible ways }.$$

For instance, in the first case, we need the solution for the second one, because cut in $1$ (i.e. $[1$ and $n-1]$) means $\text{price}(1)+l(n-1)$, where $l$ is the method that solves our problem for a rod of length $n$. But solves $l(n-1)$ should consider cut in $1$ again, but this time in a length of $n-2$, that is, $\text{price}(1) +l(n-2)$. As we can see $l(1)$ was already required, and if we continue, it will be required again. Also, it repeats with $l(n-2)$ and others, overlapping subproblems.

$$l(n)=\max \{\ \underbrace{\text{price}(1)+ \color{blue}{l(n-1)}}_{\text{cut in } 1},\ \text{price}(2) + \color{red}{l(n-2)}, \text{price}(3) + \color{green}{l(n-3)}, \cdots,\underbrace{\text{price}(n-1) + l(1)}_{\text{cut in }n-1} \}.$$

And, $$\color{blue}{l(n-1)}=\max \{\ \underbrace{\text{price}(1)+ \color{red}{l(n-2)}}_{\text{cut in } 1},\ \text{price}(2) + \color{green}{l(n-3)}, \cdots, \text{price}(n-3) + l(2) \}.$$

Therefore, $$l(n) = \max_{i=1,\cdots,n-1} \text{price}(i) + l(n-i).$$ with $l(0) = 0$.

• Why is $O(n^2)$?

To build up the solution $l(n)$, we have to compute the small instances of the problem, $l(1), l(2),\cdots, l(n-1)$. In each case, we have to iterate all possible cuts $1, 2, \cdots, n - 1$. Then, we have $O(n)\cdot O(n)$ running time.

Answer 3

You are on the right track there. Using L and an array N of integers from 1 to n, you can find the max profit of any string size i, such that i<=n. At string size i, the string will either be cut or not. The max profit will be pi if it's not cut, and pj+L[i-j] for all j in N given j<=i. Then just compare the two to determine which value is greater. Here's some psuedocode

L[0]=0 for all i in N L[i]=max{pi, ((pj+L[i-j]) for all j in N given j<=i)} return L[n]

Hope this helped