2
$\begingroup$

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!

$\endgroup$
  • 1
    $\begingroup$ You say recurrence, but then something about arrays. Stay in the recurrence world: how can you make the problem smaller and combine solutions? $\endgroup$ – Raphael Apr 7 '16 at 20:57
  • 1
    $\begingroup$ Isn't this the rod-cutting problem from CLRS (3rd edition), section 15.1, page 360? $\endgroup$ – SteeleDynamics Apr 7 '16 at 23:41
  • 1
    $\begingroup$ Please edit the question to indicate where you got this question from. See cs.stackexchange.com/help/referencing. Also, please edit the question to indicate what efforts you've made to come up with a recurrence relation. Have you tried working through some examples, to see if you can find a relationship between L[i] and L[smaller values]? If not, that would be a good next step. $\endgroup$ – D.W. Apr 8 '16 at 1:28
  • $\begingroup$ Have you read the answers yet? You should probably do it or it doesn't fit of what you expected? Check the correct one. $\endgroup$ – jonaprieto Apr 14 '16 at 18:16
4
$\begingroup$

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.
$\endgroup$
  • $\begingroup$ +1 It would not be an answer, but this is a. very interesting solution to the problem, these convolutions, in which other problems have you applied to? $\endgroup$ – jonaprieto Apr 10 '16 at 13:48
  • $\begingroup$ @d555 I didn't know about max-convolution before thinking about this problem. I just noticed a similarity between the max-of-split-in-two problem and multiplying polynomials (it's identical except you use {max, +} instead of {+, *}), guessed at the operation's name, and got it right. $\endgroup$ – Craig Gidney Apr 10 '16 at 20:11
  • 1
    $\begingroup$ The linked algorithm does not actually work in $O(n \log n)$ average time in the usual sense ($O(n \log n)$ expected time independently of the input). It works in $O(n \log n)$ time when averaged over all possible inputs --- including both hard and very easy cases. It is not immediately apparent from the abstract or the introduction, though: one needs to look at the statements of the theorem 1 and lemma 4. As far as I know, computing max-convolution in $O(n^{2-\varepsilon})$ time for any $\varepsilon > 0$ is an open problem. $\endgroup$ – Kaban-5 Dec 12 '18 at 10:55
  • $\begingroup$ @Kaban-5 that is extremely interesting. Do you have additional referencesi could add? $\endgroup$ – Craig Gidney Dec 12 '18 at 17:25
  • 1
    $\begingroup$ Well, the following paper seems to be the current state-of-art on the problem: citeseerx.ist.psu.edu/viewdoc/… A survey of results related to the supposed hardness of min-plus convolution: arxiv.org/pdf/1702.07669.pdf. Also, there is a question on this very topic on cstheory with a link to further discussion on mathoverflow: cstheory.stackexchange.com/questions/19982/… $\endgroup$ – Kaban-5 Dec 12 '18 at 18:31
1
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.