The stick breaking algorithm solve the following problem:
You have a stick that is \(n\) meters long. You can make money for selling sticks of size \(1\) meter, \(2\) meters, \(\dots,\) \(n\) meters for various prices, and you can cut a large stick into smaller sticks.
How should you cut the stick to make the most money?
For example, suppose you have a stick that is \(5\)m long. You can make the following amounts of money for different lengths sticks:
$1 for 1\(m\)
$4 for 2\(m\)
$5 for 3\(m\)
$6 for 4\(m\)
$8 for 5\(m\)
How should you cut the stick for maximum profit?
▼ Solution:
The most money you can make is \($9.\) You should cut the \(5\)m stick into three sticks of sizes \(2\)m, \(2\)m, \(1\)m.
Stick breaking
Enter prices for each length stick and the algorithm will return
the maximum amount that can be made for each size, and
the cuts needed to make the maximum amount.
You cannot get money for an uncut \(11\)m stick but you can still find the maximum amount of money you can make from an \(11\)m stick by cutting it.
The Code
The stickVal array stores the values earned by selling sticks. For example, stickVal[3] stores the amount of money you receive for selling a \(4\)m stick.
Click the code or the description to see the connection.
Comments
JavaScript
>Create a maxSticks object that stores the maximum values you can get and the cuts necessary. For example, maxSticks[i].val is the maximum amount of money you can get by cutting an \((i+1)\)m stick and maxSticks[i].division is how you should cut an \((i+1)\)m stick.
>A \(1\)m stick cannot be divided, so the amount you can get for a \(1\)m stick is whatever it is worth and you cannot divide the stick.
>Compute the values of the sticks of lengths \(2\) through \(11\) using the maximum values computed for the shorter sticks.
>>CurrMax is the current maximum found so far. It is initialized to the value you could get by not cutting the stick.
>>Check all of the possible cuts to see if you could make more money. If the stick should be cut, there must be a first cut. A stick that is \(i\) meters will be cut into two smaller sticks of size \(j\) meters and \(i-j\) meters, so consider all cuts from \(j = i-1\) to \(i/2.\) For example, if \(i = 6,\) find the money you can make by cutting into lengths \(5\) and \(1,\) \(4\) and \(2,\) and \(3\) and \(3.\)
>>The max you could get for sticks of length \(j\) and \(i-j\) have already been computed and stored at indices \(j\) and \(i-j-1.\) Check whether the money you can get for these sticks is greater than the money you could get for the maximum of previously computed cuts.
>>>If you can get more money, then update the maximum amount of money found to making a first cut into pieces of size \(j\) and \(i-j.\) Also, the division will be the division of the stick of size \(j\) and the division of the stick of size \(i-j.\)
>>>After checking all possible first cuts, currMax must be the maximum. Store the maximum value into maxSticks[i].val and store the maxDiv into maxSticks[i].division.
maxSticks = []
for (var i = 0; i < 11; i++) {
maxSticks[i] = {val: 0, division: ''}
}