StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<h2>Simplifying</h2> <p>First I want to simplify the problem, to do that:</p> <ul> <li>I switch the axes and add them to each other, this results in x2 growth</li> <li>I assume it is parabola on a closed interval <code>[a, b], where a = 0</code> and for this example <code>b = 3</code> </li> </ul> <p>Lets say you are given <code>b</code> (second part of interval) and <code>w</code> (width of a segment), then you can find total number of segments by <code>n=Floor[b/w]</code>. In this case there exists a trivial case to maximize Riemann sum and function to get i'th segment height is: <code>f(b-(b*i)/(n+1)))</code>. Actually it is an assumption and I'm not 100% sure.</p> <p>Max'ed example for <code>17</code> segments on closed interval <code>[0, 3]</code> for function <code>Sqrt[x]</code> real values: </p> <p><img src="https://i.stack.imgur.com/sAEPL.gif" alt="enter image description here"></p> <p>And the segment <strong>heights</strong> function in this case is <code>Re[Sqrt[3-3*Range[1,17]/18]]</code>, and values are:</p> <ul> <li>Exact form: </li> </ul> <blockquote> <p>{Sqrt[17/6], 2 Sqrt[2/3], Sqrt[5/2], Sqrt[7/3], Sqrt[13/6], Sqrt[2], Sqrt[11/6], Sqrt[5/3], Sqrt[3/2], 2/Sqrt[3], Sqrt[7/6], 1, Sqrt[5/6], Sqrt[2/3], 1/Sqrt[2], 1/Sqrt[3], 1/Sqrt[6]}</p> </blockquote> <ul> <li>Approximated form: </li> </ul> <blockquote> <p>{1.6832508230603465, 1.632993161855452, 1.5811388300841898, 1.5275252316519468, 1.4719601443879744, 1.4142135623730951, 1.35400640077266, 1.2909944487358056, 1.224744871391589, 1.1547005383792517, 1.0801234497346435, 1, 0.9128709291752769, 0.816496580927726, 0.7071067811865475, 0.5773502691896258, 0.4082482904638631}</p> </blockquote> <p>What you have archived is a <strong>Bin-Packing problem</strong>, with partially filled bin.</p> <h2>Finding b</h2> <p>If <code>b</code> is unknown or our task is to find smallest possible <code>b</code> under what all sticks form the initial bunch fit. Then we can limit at least <code>b</code> values to:</p> <ol> <li>lower limit : if sum of segment heights = sum of stick heights</li> <li>upper limit : <s>number of segments = number of sticks </s> longest stick < longest segment height</li> </ol> <p>One of the simplest way to find <code>b</code> is to take a pivot at <code>(higher limit-lower limit)/2</code> find if solution exists. Then it becomes new higher or lower limit and you repeat the process until required precision is met. </p> <hr> <p>When you are looking for <code>b</code> you do not need exact result, but suboptimal and it would be much faster if you use efficient algorithm to find relatively close pivot point to actual <code>b</code>.</p> <p>For example:</p> <ul> <li>sort the stick by length: largest to smallest</li> <li>start 'putting largest items' into first bin thy fit</li> </ul>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload