help knapsack problem solution solver

[aperocket]

Is this doable through simple script or field calculation? I don't know where to start but I'm hoping to exact solution about this.

Here my example. I have a stock of 70", 100", 2pcs of 150" and 12pcs of 240". Also i have orders that needs

39", 88", 91", 106", 55", 55", 72", 72", 72", 144", 144", 144", 32", 66", 66", 66", 66", 144", 144", 144", 50", 50", 81", 81", 132", 132", 132", 168", 196". In the real world my goal is to minimize the wastage. So it will end up similar to this results.

#1 - 70" = 66", with 4" wastage            
#2 - 100" = 66", 32" with 2" waste        
#3 - 150" = 81", 66" with 3" waste            
#4 - 150" = 81", 66" with 3" waste            
#5 - 240" = 196", 39" With 5" waste            
#6 - 240" = 168", 72" with no waste            
#7 - 240" = 144", 91" with 5" waste            
#8 - 240" = 144", 88" with 8" waste            
#9 - 240" = 144" with 96" waste            
#10 - 240" = 144" with 96" waste            
#11 - 240" = 144" with 96" waste            
#12 - 240" = 144" with 96" waste            
#13 - 240" = 132", 50", 55" with 3" waste            
#14 - 240" = 132", 50", 55" with 3" waste            
#15 - 240" = 132", 106", with 2" waste            
#16 - 240"= 72", 72 with 96" waste    

 

 

 

[rwoods]

Hello

Sorry to be slightly unhelpful, but what you have there is a mathematical problem, not a FileMaker problem. First you need to solve the issue of how best to utilise your raw materials to fulfil the orders, and then work out the best way to do it in FileMaker.

Maybe you do this to try some ideas:-

Create a table of raw materials with fields :-

id (text), startLength (num), unusedLength (num), ordersFulfilled (text, list of id's)

unusedLength starts with the same value as startLength.

 

Create table of orders with fields :-

id (text), requiredLength (num), isFulfilled (num boolean, starts FALSE)

Sort your table of raw materials biggest first, and then LOOP through them in FileMaker

For each raw material in the loop, find the biggest order that can be fulfilled from it from the orders table, looking at only the orders where isFulfilled is FALSE. Mark the chosen order as isFulfilled = TRUE. Add the id of the fulfilled order to the ordersFulfilled list on the raw material, in case we want to refer to that later. Subtract the length of the order from the unusedLength field of the raw material.

After finding the biggest fulfillable order, then find the next biggest and do everything above again. When you cannot find any further orders that can be fulfilled (as they are all too big, or your raw material has been used up (unusedLength hits zero) ) then stop and go back to the beginning of the loop.

You now carry on to the next Raw Material record, and do the same again.

When finished, you will have fulfilled all the orders you can (they will be marked as isFulfilled = TRUE), and you will know the wastage from each raw material (it's whatever is left in the unusedLength field).

 

The problem you have is optimising this. The routine above will come up with a solution, but not the best solution. Unless you can find an algorithm on the internet that elegantly solves this, then you need to use some trial and error.

 

Run the above system, and then count how much raw material you are left with, that is the wasted raw material (SUM the unusedLength field from all raw materials). You may also have some orders that you couldn't fulfil, add up the total unfulfilled order lengths. Now remember those two figures somewhere, and re-run the loop, but this time fulfil the smallest order first for each raw material, not the biggest, and then try the next smallest until you run out of raw material.

After doing that, have you got less wastage and/or more orders fulfilled? Remember that result too.

I would then use a random number generator to try it again with randomly selected orders (instead of sorting them in any particular order), rejecting them if they are too big, and seeing what wastage you get then.

 

FileMaker can do all this for you, but it is the 'algorithm-inventor' within you that will be the biggest help!

 

Edited June 30, 2020 by rwoods

[Wim Decorte]

further to what @rwoods is saying: since this is a pure math problem, consider looking for 'solved problems' in other environments.

For instance: https://gist.github.com/lqt0223/21f033450a9d762ce8aee4da336363b1

Using a JavaScript solution like this inside FM is easy, especially in 19.  Or if you find a good piece of code in any other technology stack you prefer then spin it up as a web service and integrate with it.

That may ultimately be faster to develop and deploy.

[aperocket]

Hello, Thanks for the ideas. I'm still checking the possibilities for mathematical solution before applying it to filemaker.