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

Postby nfunk » Jun 05, 2020 20:33

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: 2933
Joined: Jun 02, 2015 16:24

Re: Optimum sum of a set of numbers

Postby Tourist Trap » Jun 06, 2020 15:28

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: 6688
Joined: Jan 10, 2006 20:30
Location: Scotland

Re: Optimum sum of a set of numbers

Postby dodicat » Jun 06, 2020 16:10

Blitz your 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 n
End Sub

Sub 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 n1
End Sub

Dim As Long a(1 To 10)= _
{175, _
250, _
79, _
325, _
652, _
125, _
410, _
519, _
10, _
701}

Redim As Long holder() 'to hold the result


Randomize
Dim As Long n
Dim As Long sum

For 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
    Print
Next i

Sleep


 
grindstone
Posts: 752
Joined: May 05, 2015 5:35
Location: Germany

Re: Optimum sum of a set of numbers

Postby grindstone » Jun 06, 2020 16:14

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, optmask
Dim As Integer y, sum, optsum, maxsum = 1000

Print 'without this PRINT I get a false positive from COMODO virus scanner

For x = LBound(number) To UBound(number) 'set mask for numbers array
   mask = BitSet(mask, x)
Next

For 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
   EndIf
Next

For y = LBound(number) To UBound(number)
   If Bit(optmask, y) Then
      Print number(y); " +";
   EndIf
Next

Locate CsrLin, Pos() - 2
Print " ="; optsum

Sleep


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: 6688
Joined: Jan 10, 2006 20:30
Location: Scotland

Re: Optimum sum of a set of numbers

Postby dodicat » Jun 06, 2020 16:27

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

Postby grindstone » Jun 06, 2020 16:36

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

Postby nfunk » Jun 06, 2020 17:11

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

Postby nfunk » Jun 06, 2020 17:28

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

Postby grindstone » Jun 06, 2020 17:42

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

Re: Optimum sum of a set of numbers

Postby Tourist Trap » Jun 06, 2020 17:53

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 maximum
dim as integer M = 400

'build a set of numbers
dim 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 Object
type Memorizer
    declare constructor( )
    declare constructor( SubsetArray() as integer )
    declare operator cast() as string
    as integer  sum
    as integer  arrayOfIntegers(any)
end type
constructor Memorizer( )
    '
end constructor
constructor 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 index
end constructor
operator 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 s
end 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 subset
redim 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 subsets
dim 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 i
for 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 purpose
dim as integer max = -1
for index as integer = lBound(arrayOfMemorizers) to uBound(arrayOfMemorizers)
    ? arrayOfMemorizers(index).sum, arrayOfMemorizers(index)
    if max<arrayOfMemorizers(index).sum then max = arrayOfMemorizers(index).sum
next index


screenRes 800, 600, 32


view (100,100)-(100 + valint(binaryIndexer), 100 + max), 1, 15
Window ( 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), _
            bf
next index
for index as integer = lBound(arrayOfMemorizers) to uBound(arrayOfMemorizers)
    if index mod 30 = 0 then
        draw string ( index, 12), str(index)
    end if
next index
line (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

Postby RockTheSchock » Jun 06, 2020 18:14

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.
badidea
Posts: 2149
Joined: May 24, 2007 22:10
Location: The Netherlands

Re: Optimum sum of a set of numbers

Postby badidea » Jun 06, 2020 18:34

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: 6688
Joined: Jan 10, 2006 20:30
Location: Scotland

Re: Optimum sum of a set of numbers

Postby dodicat » Jun 06, 2020 19:16

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=10000

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 n
End Sub

Sub 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 n1
End Sub

function findnearest(a() as long,holder() as long,value as long )  as long
Randomize
Dim As Long n
Dim As Long sum
For 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=1
Next i
return 0
end function

function findbiggest(a() as long,holder() as long,value as long)  as long
Randomize
Dim As Long n
Dim 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=1
return 0
end function


Dim As Long a(1 To 10)= _
{175, _
250, _
79, _
325, _
652, _
125, _
410, _
519, _
10, _
701}

Redim As Long holder() 'to hold the result

dim 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
    print
end if

print

 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
    print
end if
print
print "Press any key to finish . . ."


Sleep

 
Muttonhead
Posts: 130
Joined: May 28, 2009 20:07

Re: Optimum sum of a set of numbers

Postby Muttonhead » Jun 06, 2020 21:16

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: 624
Joined: May 05, 2017 19:59
Location: Germany

Re: Optimum sum of a set of numbers

Postby UEZ » Jun 06, 2020 23:05

Here my version:

Code: Select all

'https://rosettacode.org/wiki/Permutations#FreeBASIC
Sub 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: " & iter
End 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.

Return to “General”

Who is online

Users browsing this forum: No registered users and 1 guest