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.
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:
x[1] >= number of 1m lengths needed
x[2] >= 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