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.
``````
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
Posted on 2001-04-30 10:27:00 by forge
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
Posted on 2001-04-30 11:23:00 by 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.``````
``` Posted on 2001-04-30 13:37:00 by bitRAKE ```
``` Different sort of optimisation 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. 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 Posted on 2001-04-30 23:45:00 by tank Different sort of optimisation 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 Posted on 2001-05-01 07:44:00 by forge Different sort of optimisation 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. :) Posted on 2001-05-29 15:56:00 by bitRAKE Different sort of optimisation 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 Posted on 2001-05-29 18:05:00 by NaN Different sort of optimisation 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 Posted on 2001-06-03 06:56:00 by forge Different sort of optimisation 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: Posted on 2001-06-03 20:28:00 by SFinegan Different sort of optimisation Excellent thank you SFinegan forge Posted on 2001-06-03 22:05:00 by forge ```
``` <!-- google_ad_client = "ca-pub-5565452985039448"; /* Header */ google_ad_slot = "3725908010"; google_ad_width = 728; google_ad_height = 90; //--> var _gaq = _gaq || []; _gaq.push(['_setAccount', 'UA-11286174-1']); _gaq.push(['_trackPageview']); (function() { var ga = document.createElement('script'); ga.type = 'text/javascript'; ga.async = true; ga.src = ('https:' == document.location.protocol ? 'https://ssl' : 'http://www') + '.google-analytics.com/ga.js'; var s = document.getElementsByTagName('script')[0]; s.parentNode.insertBefore(ga, s); })(); ```