Find to the nearest sum

[archrid404]

Is there a way to accomplish this? 

I.E. 

Total = 120 

Value = 50, 60, 60

result should be = 60, 60

 

or Total  = 100

value = 30; 50, 60, 20, 20

result = 60, 20, 20

 

[Fitch]

Is that semi-colon in ex. 2 a typo?

Could the result of ex. 2 also be 30, 50, 20 ?

I suppose what you'd do is create a script that would attempt all combinations of the values and then return those that match the total.

[archrid404]

20 minutes ago, Fitch said:

Is that semi-colon in ex. 2 a typo?

Could the result of ex. 2 also be 30, 50, 20 ?

I suppose what you'd do is create a script that would attempt all combinations of the values and then return those that match the total.

yeah your correct, it could be also 30, 50, 20

[archrid404]

I was thinking a custom sum function the result will be atleast the closest to total like

Sum ( List ; Total )

result will be alteast the nearest to total

I.E Sum (  30 "¶" 50 "¶" 60 "¶" 20 "¶" 20  ; 100 ) result =  60, 20, 20  "¶" 30, 50, 20

 

[comment]

How many values do you expect to have at most?

[archrid404]

As long as there's possible combination. But i think i will get the closest to the total. 

[comment]

I don't think you understood my question. Your first example has 3 values. Your second example has 5 values. What is the maximum number of values you will ever have?

[archrid404]

10 hours ago, comment said:

I don't think you understood my question. Your first example has 3 values. Your second example has 5 values. What is the maximum number of values you will ever have?

Actually no maximum values. I get those on portal.

[comment]

Well, I suggest you put some restriction on the number of allowed values, because otherwise this gets (even more) complicated.

Some background:
Your question is a variation of the subset sum problem, which in turn is a special case of the knapsack problem. Both are VERY difficult problems to solve programatically.  Even worse, the known solutions are difficult to implement in Filemaker, because its calculation engine has no arrays.

Fortunately, with a small number of values, a naive brute-force solution is feasible: enumerate all possible combinations of the given values, calculate the sum of each combination, and compare it to the target sum.

The attached demo is designed to deal with up to 7 values. It has 127 records to enumerate the 2^7 -1 = 127  possible combinations, and a repeating calculation field with 7 repetitions to list the values of each combination. You can extend the limit by adding more records and more repetitions, but - as I said - this is a brute-force approach and it will get slower as the number of values increases.

 

 

SubsetSum.fmp12

[archrid404]

2 hours ago, comment said:

Well, I suggest you put some restriction on the number of allowed values, because otherwise this gets (even more) complicated.

Some background:
Your question is a variation of the subset sum problem, which in turn is a special case of the knapsack problem. Both are VERY difficult problems to solve programatically.  Even worse, the known solutions are difficult to implement in Filemaker, because its calculation engine has no arrays.

Fortunately, with a small number of values, a naive brute-force solution is feasible: enumerate all possible combinations of the given values, calculate the sum of each combination, and compare it to the target sum.

The attached demo is designed to deal with up to 7 values. It has 127 records to enumerate the 2^7 -1 = 127  possible combinations, and a repeating calculation field with 7 repetitions to list the values of each combination. You can extend the limit by adding more records and more repetitions, but - as I said - this is a brute-force approach and it will get slower as the number of values increases.

 

 

SubsetSum.fmp12 156 kB · 1 download

It's working. Yeah i notice the problem now that if i increase the repetition number it becomes slower.

It's it possible not to use repetition field? Instead we will just use an calculation text field.

[comment]

4 hours ago, archrid404 said:

It's it possible not to use repetition field? Instead we will just use an calculation text field.

What makes you think that would be any faster?

 

[archrid404]

26 minutes ago, comment said:

What makes you think that would be any faster?

 

So the it will be the same even if i change it to calculation text field?

[comment]

I don't know. No matter how, you still need to calculate all possible combinations and their sums. I believe my method is more efficient than what you suggest, but I haven't tested it (and not going to).

 

[archrid404]

I was thinking to use the list function I.E List (Number) result will be something like

50

30

30

60

Then loop it to get the nearest total to given number. like 100 = 30, 60

On 11/26/2019 at 8:02 AM, Fitch said:

Is that semi-colon in ex. 2 a typo?

Could the result of ex. 2 also be 30, 50, 20 ?

I suppose what you'd do is create a script that would attempt all combinations of the values and then return those that match the total.

The result is in list form but im afraid it could take time because i am going to loop the number to get to the total nearest.

[archrid404]

On 11/27/2019 at 3:34 PM, comment said:

I don't know. No matter how, you still need to calculate all possible combinations and their sums. I believe my method is more efficient than what you suggest, but I haven't tested it (and not going to).

 

Is it possible just to get the most closest result?

[comment]

In my demo, after you press "Find Equal or Less", the first record in the found set will be the closest result (or one of several closest results), excluding results that are greater than the target sum.

[archrid404]

53 minutes ago, comment said:

In my demo, after you press "Find Equal or Less", the first record in the found set will be the closest result (or one of several closest results), excluding results that are greater than the target sum.

Is it possible to eliminate not closest to the result?

[comment]

You could grab the result from the first record and perform another find for it. Or start looping among the records and as soon as you get to a record with a different result, omit it and all the records that follow it.