complicated calculation

Hi,
anybody that would help would be very much thanked...
I would like to find a way to solve a problem I am very often confronted with, and always have to solve by hand.
Among a range of products, I have several possible lengths. For one product, I need to have several lengths. How can I calculate the most economic combination ?
Example: I need 80+65+79+254+158+345+53 within a range of 240, 270, 300, 330, 360, 400. What should be the best combination so that the final total length is the smallest possible ?
Good luck

could you please explain in more detail?

Mangesh

sure, but I wouldn't really know what more to say.
I calculate very often quantities of materials to buy, for instance wood, after considering all the small pieces I need. Then, I have to check what are the available lengths with a retailer, and I have to calculate myself what a working combination is. For available lenghts of 240, 270, 300, 360, 400, I need a combination for 80+65+79+254+158+345+53.
Result can be 254+79=333, so i buy 360. then 80+65+158+53=356, so i buy 360 again. rest 345, so i need again 360. But with other needs, I might beter buy 1 of 240, 5 of 360, 2 of 400.
Is it clear ?

Originally Posted by Myles

From all indications, your problem appears to have a look of SOLVER about it.You have, however, thus far, not provided sufficient light to permit a formulation for Solver.



What does the 1st group (comprising 7 items) represent? And how do they relate to the 2nd group? Are you attempting to get the WHOLE 7 lengths of the 1st group from items in the 2nd such that the LEAST of the items in the 2nd group is used?

Better still, mail us your Excel file showing data layout and formula web.

I think he's trying to fit the whole 7 lengths of the first group into lengths from the second group such that the total of the lengths in the second group are as low as possible.

The major problem with this puzzle is that it's technically impossible to create an algorithm to perfectly solve the problem in non-exponential time (I studied discrete maths very recently, I remember this problem coming up!) What's more, it's not even possible to figure out how to sort them optimally even if the lengths in group B were all the same except in exponential time, which will grow unwieldly very rapidly.

Best thing you could do would probably be a first-fit algorithm; going from the largest length to the smallest, fit each length into group 1 into the smallest length remaining between new lengths from group 2 and partially-used lengths from group 2. I'll have a look at it later on and see if I can formalise it somewhat so I can work on a macro. This won't be 100% efficient, but should be pretty close most of the time.

Originally Posted by McManCSU

This should not be a very tough problem to solve. The previous poster is thinking more in math terms yet this is more of a programming solution.

I don't deny that I'm thinking in maths terms, but remember I am thinking about discrete mathematics, which is significantly about algorithms and is highly useful with this sort of programming.

If you do the following:
Have each length that you can buy in one column, then in the next column, have the corresponding price for that length. You can calculate a per unit cost.

Using that per unit cost, you can fit as much as possible into the cheapest per unit length (since it is the cheapest per unit). Then with the remaining pieces that you still need to buy, you can have the program fit them into the next cheapest per unit length, and so on. I think that if you go off the notion that the more you can fit into a length, the cheaper, this should give an optimal solution (I think). If for example there are multiple combinations which each can fit into a particular length, take the combo with the greatest summed length.
ie. targetLength= 250, and you need 50+100+90 and 50+100+80, you would first use the ...+90 one.

If you can think of a case where this algorithm would fail, post it. Hope this helps.

... I think this is basically the same algorithm as the one I posted. It's not 100% efficient, but is guaranteed to be at absolute worst 50% efficient, and will generally be somewhere in the region of 95% efficient on average.

But yes, I did instinctively approach this problem from the mathematician's perspective, which in hindsight gave a very negative-sounding answer.

Im not knocking the math , just giving a different approach to the solution.