This is not strictly Win32Asm, and I can't even describe the category of math which it belongs to, but still I'm hoping that somebody can help and I would appreciate very much any lead, help or advice. I want to incorporate it in ASM project code, which I believe I'm able then to convert this algorithm into Win32Asm. (I will try to explain in a very primitive way) The problem is: The supplier is able to supply 10 meters length pieces. and I have to cut them into various shorter lengths - and I want to cut them in the most economical way so that I don't need to buy too many 10m lengths. The solution could be: - if for example the client wants these size pieces.
So I cut 16 pieces and I used 3 and 4/10th of the 10m lengths pieces. The point is: How can the solution be calculated using the length in the most economical way if a large number of pieces is required. - say 200 This I believe is a long calculation procedure, as every possibility would need to be calculated. Thank you forge
You fit into a 10m - 1x4m 2x2m 2x1m =10 next 10m - 1x5m 2x2m 1x1m =10 next 10m - 2x3m 4x1m =10 next 10m - 1x4m =4 - and I'm left with 6m.
One (fairly simple), and quick(ish) way, would be using automata. Create some series of states, and transitions across those states. Then allow certain transitions between states. It is this kind of system that grep uses to search text (VERY) quickly. If you weight your transitions, so it is obviously favourable to deal with big lengths first, then simply loop until there is nothing left! Customer wants: 1x9m 2x8m 6x4m 1x1m Your code: (1) Length = 10 if (an order can be processed) -> Subtract largest possible from length & decrement customer order. else -> record waste -> if (there are orders left) -> -> goto (1) -> exit! This situation is a fairly simple one. It is always most favourable to remove the largest elements first, then "mop up" slack with smaller elements. This really is quite a simple automata, but you can build a much more complex system of transitions. Imagine if there are several types of wire, and some cannot go above length n! Then associate some cost with the cutting, make them available in different lengths (10m, 20m, or 50m), then you've got a problem.... P = NP anyone? :P Mirno
Mirno, what if the needed sizes are:
5 - 4m 10 - 3m
How does this algo process that 4+3+3=10, rather than 4+4+(waste 2m)=10? Using largest first is good, but no waste is better.
The math-computing category is (ambiguously) called "programming". Books on the subject call it "mathematical programming". The simplest version is "linear programming", so-called because the formulae used are linear (no exponents on the variables). Books on "operations research" also introduce you to this subject. It's been a while...it's not obvious to me how to formulate all of the constraints. Some constraints are obvious:
Edit: Oh, yes. Some books also call it "optimization" or "optimisation". This message was edited by tank, on 4/30/2001 11:52:43 PM
x >= number of 1m lengths needed x >= number of 2m lengths needed etc.
Thank you Mirno, bitRAKE and tank. I have learnt a lot from your replies. To implement a simple optimisation into my code will represent a few years study of mathematical programming and it is not an easy task. Why can't the computer think. I know it is so easy to take a sheet of paper and a pencil and work it out - how many lengths are into 10 next 10 next 10 etc. Silly me, I thought it would be only some additions and subtractions in a few loops to solve the problem. forge
I think you could do it without all that studying - well, at least this problem. Try to think of the way you solve it and just code something similar. Work through some examples writing down your calculation choices and why you made that choice - you will quickly see an algorithm that will work. Or, post your findings here - I love these kinds of problems, and would be happy to help. :)
Backing away from com-sci a bit. The answer to your problem can also lie in Multi-Variable Calculus. To be exact, Parametric equations ie) y=f( a, b, c, d, ... ). The learning curve on this can be a bit rough tho if your not familiar with standard calculus. But if your are, take the partial derivitaves and determin a mamxima. This will be you best yeild. Just letting you know, sounds like there are more down to earth solutions floating around as is. NaN
Thank you bitRAKE, ------------------ I think you could do it without all that studying - well, at least this problem. I have been thinking about what you said, but I don't think I will do a top job. Probably not even a good job, as I don't even know where to start. Thank you NaN, -------------- You have excellent thinking, sadly I have to admit that this way is beyond the scope of my knowledge of math. forge
I was going to write you a program to cut your stuff, but thought I would run a search first. Glad I did. Includes source. Go to the following link: http://www.geocities.com/CapeCanaveral/Hall/4425/ Scroll down to Cuts.zip 30K, and download. I didn't test the software but I did look at the top of the Cuts.txt file. This may do the job. :cool:
Excellent thank you SFinegan forge