## Optimum sum of a set of numbers

General FreeBASIC programming questions.
nfunk
Posts: 6
Joined: Jun 05, 2020 20:25

### Optimum sum of a set of numbers

HELP!!!

I haven’t programmed since college days back in the 1970’s. With my mind stagnating from sitting at home due to COVID, I decide to take on a little task of programming.

I am a fairly new to Freebasic, even though I once programmed in compiled Basic, but I am at a total lost in trying to come up with a Freebasic algorithm for computing an optimum set of numbers that when summed will not exceed a particular number.

For example, I have this set of numbers:
175
250
79
325
652
125
410
519
10
701

I need to get the optimum sum of these numbers not to exceed a particular number like 1000. I can do this manually on a calculator through many iterations, but I cannot come up with a Freebasic algorithm or program to do this task.

I know many of your Freebasic Guru’s will find this very elementary in nature, so please forgive my idiocrasy.
Tourist Trap
Posts: 2922
Joined: Jun 02, 2015 16:24

### Re: Optimum sum of a set of numbers

nfunk wrote:I need to get the optimum sum of these numbers not to exceed a particular number like 1000.

Hello,

nice idea to get the brain training on this kind of problems in FB. It's quite rewarding.

I don't understand something, here above however. Do you mean you want to find a subset of your list of numbers such that when added they are closer to 1000 than any other subset? Right?

For instance with this initial list: { a, b, c, d , e }
You want to get a subset, { a, b, c } for instance, then sum over it : S = a + b + c, and get D = 1000 - S.
Then you save this subset as a possible solution if D>=0, and after testing every candidates subsets you keep the one that has the smallest value for D. That's your subset.

After that, you can also add a condition, if there are many subsets with same smallest D. You may want then to choose the subset with the smallest amount of numbers inside, or any other criteria.

Do you agree with this way of describing the job?
dodicat
Posts: 6687
Joined: Jan 10, 2006 20:30
Location: Scotland

### Re: Optimum sum of a set of numbers

Code: Select all

`Sub shuffle(a() As Long)    #define range(f,l) Int(Rnd*((l+1)-(f)))+(f)    For n As Integer = Lbound(a) To Ubound(a)-1        Swap a(n), a(range(n,Ubound(a)))    Next nEnd SubSub bsort(a() As Long)    For n1 As Long=Lbound(a) To Ubound(a)-1        For n2 As Long=n1+1 To Ubound(a)            If a(n1)>a(n2) Then Swap a(n1),a(n2)        Next n2    Next n1End SubDim As Long a(1 To 10)= _{175, _250, _79, _325, _652, _125, _410, _519, _10, _701}Redim As Long holder() 'to hold the resultRandomizeDim As Long nDim As Long sumFor i As Long=1 To 10        n=Ubound(a)        Do        For m As Long=1 To 10000            shuffle(a())            sum=0            For k As Long=1 To n                sum+=a(k)            Next                        If sum<1000 Then                Print "SUM ",sum,m; "  iterations",n;"  elements:"                Redim holder(1 To n)                 For k As Long=1 To n                    holder(k)=a(k)                Next                bsort(holder())                For k As Long=1 To n                    Print holder(k);                Next                Print                Exit Do            End If                    Next m        n-=1            Loop Until n=1    PrintNext iSleep  `
grindstone
Posts: 752
Joined: May 05, 2015 5:35
Location: Germany

### Re: Optimum sum of a set of numbers

Brute force and limited to 64 values:

Code: Select all

`Dim As Integer number(0 To ...) = {175, 250, 79, 325, 652, 125, 410, 519, 10, 701}Dim As ULongInt mask, x, optmaskDim As Integer y, sum, optsum, maxsum = 1000Print 'without this PRINT I get a false positive from COMODO virus scannerFor x = LBound(number) To UBound(number) 'set mask for numbers array   mask = BitSet(mask, x)NextFor x = 0 To mask 'brute force, check all possible combinations   sum = 0   For y = LBound(number) To UBound(number)      If Bit(x, y) Then         sum += number(y) 'add corresponding value if bit in "x" is set         If sum > maxsum Then            Continue For, For 'next "x"         EndIf      EndIf   Next   If (maxsum - sum) < (maxsum - optsum) Then 'new sum is closer to former optimum      optmask = x      optsum = sum   EndIfNextFor y = LBound(number) To UBound(number)   If Bit(optmask, y) Then      Print number(y); " +";   EndIfNextLocate CsrLin, Pos() - 2Print " ="; optsumSleep`

EDIT: Oops, dodicat was faster.

EDIT 2: @dodicat: Your program seems not to calculate correct. I get a closest sum of 175 + 79 + 325 + 410 + 10 = 999.
dodicat
Posts: 6687
Joined: Jan 10, 2006 20:30
Location: Scotland

### Re: Optimum sum of a set of numbers

Nice one grindstone.
I was concentrating on getting the maximum number of elements to suit.
grindstone
Posts: 752
Joined: May 05, 2015 5:35
Location: Germany

### Re: Optimum sum of a set of numbers

Thank you. I wonder if there's a more elegant method than brute force.
nfunk
Posts: 6
Joined: Jun 05, 2020 20:25

### Re: Optimum sum of a set of numbers

Yes, I want to get the sum of the most numbers to be the nearest to, or equal to 1000 without exceeding 1000.

Tourist Trap wrote:
nfunk wrote:I need to get the optimum sum of these numbers not to exceed a particular number like 1000.

Hello,

nice idea to get the brain training on this kind of problems in FB. It's quite rewarding.

I don't understand something, here above however. Do you mean you want to find a subset of your list of numbers such that when added they are closer to 1000 than any other subset? Right?

For instance with this initial list: { a, b, c, d , e }
You want to get a subset, { a, b, c } for instance, then sum over it : S = a + b + c, and get D = 1000 - S.
Then you save this subset as a possible solution if D>=0, and after testing every candidates subsets you keep the one that has the smallest value for D. That's your subset.

After that, you can also add a condition, if there are many subsets with same smallest D. You may want then to choose the subset with the smallest amount of numbers inside, or any other criteria.

Do you agree with this way of describing the job?
nfunk
Posts: 6
Joined: Jun 05, 2020 20:25

### Re: Optimum sum of a set of numbers

Guys!,

Thank you. The algorithms work great. I will have to set down and analyze the inner workings.
Side note: To show my age, many years ago I wrote a huge database management program for a large utility. It included quick, and bubble sort, binary search sort, some written in Assembly language and compiled to greatly increase sort speed, and a telecommunications routines for dial up modem using compression with CRC checksum verification to the field offices. Now, about 95% of this knowledge has gone to waste. I guess the old adage "use it or loose it" is true.

Again,
Thank y'all for the prompt help!!!
Nick

Tourist Trap wrote:
nfunk wrote:I need to get the optimum sum of these numbers not to exceed a particular number like 1000.

Hello,

nice idea to get the brain training on this kind of problems in FB. It's quite rewarding.

I don't understand something, here above however. Do you mean you want to find a subset of your list of numbers such that when added they are closer to 1000 than any other subset? Right?

For instance with this initial list: { a, b, c, d , e }
You want to get a subset, { a, b, c } for instance, then sum over it : S = a + b + c, and get D = 1000 - S.
Then you save this subset as a possible solution if D>=0, and after testing every candidates subsets you keep the one that has the smallest value for D. That's your subset.

After that, you can also add a condition, if there are many subsets with same smallest D. You may want then to choose the subset with the smallest amount of numbers inside, or any other criteria.

Do you agree with this way of describing the job?
[/quote]
grindstone
Posts: 752
Joined: May 05, 2015 5:35
Location: Germany

### Re: Optimum sum of a set of numbers

So welcome back at coding. *smile*
Tourist Trap
Posts: 2922
Joined: Jun 02, 2015 16:24

### Re: Optimum sum of a set of numbers

nfunk wrote:Again,
Thank y'all for the prompt help!!!
Nick

Those guys are too fast :)

So here is my contrib. Something is wrong, I'm having some weird issue with the subset generation. I guess I wanted to do something like shown at grindstone example but failed.

However I added some simple graphics at the end.

Code: Select all

`? "Subset finder and adder"? "-----------------------"'set a value as the maximumdim as integer M = 400'build a set of numbersdim as integer  myArrayOfIntegers(1 to 9) = {11,22,33,44,55,66,77,88,99}'we find it convenient to create a datastructure to keep associated a subset to its sum in the same Objecttype Memorizer    declare constructor( )    declare constructor( SubsetArray() as integer )    declare operator cast() as string    as integer  sum    as integer  arrayOfIntegers(any)end typeconstructor Memorizer( )    'end constructorconstructor Memorizer( SubsetArray() as integer)    'feed the array of Integer of this Memorizer object instance    for index as integer = lBound(SubsetArray) to uBound(SubsetArray)        'add one room to the array of Integer of the Memorizer        redim preserve THIS.arrayOfIntegers(uBound(THIS.arrayOfIntegers) + 1)        'put a value if this last added room, the value being taken from the SubsetArray sent to the Object        THIS.arrayOfIntegers(uBound(THIS.arrayOfIntegers)) = SubsetArray(index)    next index    'initialize the sum stored in this instance being under construction right here    THIS.sum = 0    'deduce the sum    for index as integer  = lBound(THIS.arrayOfIntegers) to uBound(THIS.arrayOfIntegers)        THIS.sum += THIS.arrayOfIntegers(index)    next indexend constructoroperator Memorizer.cast() as string    dim as string s = ""    for index as integer = lBound(THIS.arrayOfIntegers) to uBound(THIS.arrayOfIntegers)        s &= THIS.arrayOfIntegers(index) & " "    next index    return send operator'we will work with an array of all the Memorized Object = (subset, sum)dim as Memorizer    arrayOfMemorizers(any)'we need a temporary storage for a given subsetredim as integer      SubSet(1 to uBound(myArrayOfIntegers) - lBound(myArrayOfIntegers) + 1)'in the loop below, we feed the array of Memorizers with unique Subsets deduced from the initial full set'we'll use a binary indexed word representation of the subsetsdim as string   binaryIndexer = "&b"for index as integer = lBound(myArrayOfIntegers) to uBound(myArrayOfIntegers)    binaryIndexer &= "1"next index? "Nota: there is "; trim(str(valint(binaryIndexer) + 1)); " possible subsets"? binaryIndexer#print typeof(chr(binaryIndexer[2]))dim as integer ifor index as integer = 0 to valint(binaryIndexer)    dim as integer currentIndexer = cInt( bin(index) )    redim preserve arrayOfMemorizers(uBound(arrayOfMemorizers) + 1)    '    for index2 as integer = lBound(SubSet) to uBound(SubSet)        SubSet(index2) = cInt(mid("&b"+bin(index), index2 - lBound(SubSet) + 3, 1))*myArrayOfIntegers(lBound(myArrayOfIntegers) + index2 - lBound(SubSet))        ? SubSet(index2);    next index2    ? , i    i += 1    arrayOfMemorizers(uBound(arrayOfMemorizers)) = Memorizer(SubSet())    redim SubSet(1 to uBound(myArrayOfIntegers) - lBound(myArrayOfIntegers) + 1)next index'retrieve max for graphics purposedim as integer max = -1for index as integer = lBound(arrayOfMemorizers) to uBound(arrayOfMemorizers)    ? arrayOfMemorizers(index).sum, arrayOfMemorizers(index)    if max<arrayOfMemorizers(index).sum then max = arrayOfMemorizers(index).sumnext indexscreenRes 800, 600, 32view (100,100)-(100 + valint(binaryIndexer), 100 + max), 1, 15Window ( 0, 0 ) - ( valint(binaryIndexer), max )for index as integer = lBound(arrayOfMemorizers) to uBound(arrayOfMemorizers)    line (index - lBound(arrayOfMemorizers), 0)-step(4, arrayOfMemorizers(index).sum), _             rgb(200 - index/4,0,0), _             bfnext indexfor index as integer = lBound(arrayOfMemorizers) to uBound(arrayOfMemorizers)    if index mod 30 = 0 then        draw string ( index, 12), str(index)    end ifnext indexline (0, M)-(valint(binaryIndexer), M)getKey()'eof`

grindstone wrote:Thank you. I wonder if there's a more elegant method than brute force.

Good question.
RockTheSchock
Posts: 231
Joined: Mar 12, 2006 16:25

### Re: Optimum sum of a set of numbers

There could be some possibilities to optimize the alghorithm for speed or even for memory consumption, but first you must define the parameters

define "set of numbers"
the range / any negative numbers
how many
are there duplicates
are they random or ...

define the number "optimum sum"
in what range
is it random or ...

do you plan to use the alghorithm on many different sets of numbers or just once maybe on a very large set?

You can gain a lot of speed if you sort the set first, so you can skip some iterations. But if you have many sets with only a few numbers you are better of just to use brute force. If there are negative numbers it gets even much more difficult / interesting ;-) to optimize for speed.
Posts: 2148
Joined: May 24, 2007 22:10
Location: The Netherlands

### Re: Optimum sum of a set of numbers

nfunk wrote:I need to get the optimum sum of these numbers not to exceed a particular number like 1000. I can do this manually on a calculator through many iterations, but I cannot come up with a Freebasic algorithm or program to do this task.

First step: Put away the computer and take pen and paper. Write down these iterations and try to find patterns. Try to convert this to pseudo-code. When you think you have it, go back to the computer and translate to real code. When running into problems, you may need to go back to pen and paper.

You can also try a more simple, somewhat similar algorithm first: Make a certain amount with currency bills and coins. E.g. with numbers 100, 50, 20, 10, 5, 2, 1, etc. (multiple times a bill or coin allowed).
dodicat
Posts: 6687
Joined: Jan 10, 2006 20:30
Location: Scotland

### Re: Optimum sum of a set of numbers

nfunk wrote:
I need to get the optimum sum of these numbers not to exceed a particular number like 1000. I can do this manually on a calculator through many iterations, but I cannot come up with a Freebasic algorithm or program to do this task.

I am still not sure if you want the maximum amount of numbers or the numbers closest.
so I did both.

Code: Select all

` const iterations=10000Sub shuffle(a() As Long)    #define range(f,l) Int(Rnd*((l+1)-(f)))+(f)    For n As Integer = Lbound(a) To Ubound(a)-1        Swap a(n), a(range(n,Ubound(a)))    Next nEnd SubSub bsort(a() As Long)    For n1 As Long=Lbound(a) To Ubound(a)-1        For n2 As Long=n1+1 To Ubound(a)            If a(n1)>a(n2) Then Swap a(n1),a(n2)        Next n2    Next n1End Subfunction findnearest(a() as long,holder() as long,value as long )  as longRandomizeDim As Long nDim As Long sumFor i As Long=value To 1 step -1    n=Ubound(a)    Do        For m As Long=1 To iterations            shuffle(a())            sum=0            For k As Long=1 To n                sum+=a(k)            Next            If sum=i Then                Redim holder(1 To n)                 For k As Long=1 To n                    holder(k)=a(k)                Next                bsort(holder())                return sum            End If                    Next m        n-=1    Loop Until n=1Next ireturn 0end functionfunction findbiggest(a() as long,holder() as long,value as long)  as longRandomizeDim As Long nDim As Long sum    n=Ubound(a)    Do        For m As Long=1 To iterations            shuffle(a())            sum=0            For k As Long=1 To n                sum+=a(k)            Next            If sum<=value Then                Redim holder(1 To n)                 For k As Long=1 To n                    holder(k)=a(k)                Next                bsort(holder())                return sum            End If                    Next m        n-=1    Loop Until n=1return 0end functionDim As Long a(1 To 10)= _{175, _250, _79, _325, _652, _125, _410, _519, _10, _701}Redim As Long holder() 'to hold the resultdim as long n n=findnearest(a(),holder(),1000)if n then    print "Nearest to 1000"    print "Sum = ";n;"    (";ubound(holder);" numbers)"    for n as long=lbound(holder) to ubound(holder)        print holder(n);iif(n<ubound(holder),",","");    next    printend ifprint n=findbiggest(a(),holder(),1000)if n then    print "Biggest set of numbers less than 1000"    print "Sum = ";n;"    (";ubound(holder);" numbers)"    for n as long=lbound(holder) to ubound(holder)        print holder(n);iif(n<ubound(holder),",","");    next    printend ifprintprint "Press any key to finish . . ."Sleep `
Posts: 130
Joined: May 28, 2009 20:07

### Re: Optimum sum of a set of numbers

as far as I can tell, this problem is known as the "bin packing problem".

The "best fit decreasing" approach often gives good results, but not in every case.
1.sort all sizes (or values) in descending order.
2. open a container with the appropriate fixed size
3. put the value in there. The free space in the container will of course be smaller.
4. take the next value and assign it to the open container, where it fits best, the container is best filled. If the value does not fit in any open container--> go to step 2.

As far as I understand Wikipedia, there is no Algo that always finds the optimum

Mutton
UEZ
Posts: 622
Joined: May 05, 2017 19:59
Location: Germany

### Re: Optimum sum of a set of numbers

Here my version:

Code: Select all

`'https://rosettacode.org/wiki/Permutations#FreeBASICSub Permutations()     Dim As Uinteger i, ii, j, jj, count = 1    Dim As Uinteger a(0 To ...) = {175, 250, 79, 325, 652, 125, 410, 519, 10, 701}, n = Ubound(a), c(0 To n -1)      Dim As Uinteger sum = 0, target = 1000, nearest = target, found = 0, nsum, iter = 0   Dim As String numbers = "", nnumbers = ""   ? "Numbers: ";   For i = 0 To Ubound(a)      ? a(i) & " ";   Next   ?   ? "Searching for one sum of " & target & ". Please wait some seconds..."    i = 0    While i < n      iter += 1        If c(i) < i Then            If (i And 1) = 0 Then                Swap a(0), a(i)            Else                Swap a(c(i)), a(i)            End If                  For ii As Uinteger = 0 To Ubound(a) - 1            sum = a(ii)             numbers = Str(a(ii))            For jj As Uinteger = ii + 1 To Ubound(a)               sum += a(jj)               numbers &= " + " & Str(a(jj))               If target - sum < nearest Then                  nearest = target - sum                  nnumbers = numbers                  nsum = sum               End If               If sum = target Then                   ? "Found one: " & numbers & " = " & sum                  found = 1                  Exit While               End If            Next         Next                     c(i) += 1            i = 0        Else            c(i) = 0            i += 1        End If    Wend   If found = 0 Then       ? "At least found one nearest sum: " & nnumbers & " = " & nsum   End If   ? "Iterations: " & iterEnd Sub Permutations()?? "Done."Sleep`

I didn't want to reinvent the wheel again and thus I used only the permutation code from Rosetta and injected by part into the sub. ;-)
My idea was to search for each permutation to the desired sum. If found then stop otherwise save the nearest one. I know it's an overkill because addition is commutative and it doesn't need to sum all n! permutations...^^

It will print out only one possibility.
Last edited by UEZ on Jun 07, 2020 21:27, edited 1 time in total.