Desperately Seeking Algorithm

[ControlG]

I have the following problem to solve and believe that there is probably some standard optimisation algorithm that either meets or would bend to my needs.

Assume that I have a piece of string of a given length. It must be cut into a number of pieces but each piece must fit within a certain length range. There can be more than one such non-contiguous range.

For example. Assume I have a piece of string 18.6cm long and that it must be cut so that I get pieces in the range 6-8cm or 9-10cm. This could clearly be done in more than one way (9,9.6 or 9.3,9.3 for example).

Anyone help?

[maverick]

To what accuracy you cut the string would have a bearing on the answer - could mean a possible infinite number of lengths could be cut.

[ControlG]

I am awaiting feedback from my customer as to whether there is any driving factor behind the selected solution. For example, should we aim for equal lengths if possible or least number of pieces, etc.

I used the piece of string as an analogy. I do not wish to know how many solutions there are but just a solution (as a first step anyway).

[Magnus]

This sounds a bit like the knapsack problem (http://en.wikipedia.org/wiki/Knapsack_problem), except the cut strings aren't specific lengths (since they can fall within certain ranges of length).

Is the objective just to get the maximum total length of strings with the least amount of wastage? Do you favour longer or shorter strings? Do you need at least one falling in each range? If a string needs to be 7-8 cm do you prefer 7cm, 7.5cm, or 8cm? Quite a few things will affect the algorithm's design.

It's probably best to try it by hand and design your own algorithm from there.

[ControlG]

Hi Thanks for the info.

I did sit down earlier in the week and came up with a very simple recursive solution which lends itself to tweaks to handle whether the customer prefers a bias towards long or short or mid-range lengths.

Many thanks to all