Optimum sum of a set of numbers
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.
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.
-
- Posts: 2958
- Joined: Jun 02, 2015 16:24
Re: Optimum sum of a set of numbers
Hello,nfunk wrote: I need to get the optimum sum of these numbers not to exceed a particular number like 1000.
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?
Re: Optimum sum of a set of numbers
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
-
- Posts: 862
- Joined: May 05, 2015 5:35
- Location: Germany
Re: Optimum sum of a set of numbers
Brute force and limited to 64 values:
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.
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 2: @dodicat: Your program seems not to calculate correct. I get a closest sum of 175 + 79 + 325 + 410 + 10 = 999.
Re: Optimum sum of a set of numbers
Nice one grindstone.
I was concentrating on getting the maximum number of elements to suit.
I was concentrating on getting the maximum number of elements to suit.
-
- Posts: 862
- 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.
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:Hello,nfunk wrote: I need to get the optimum sum of these numbers not to exceed a particular number like 1000.
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?
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
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
[/quote]Tourist Trap wrote:Hello,nfunk wrote: I need to get the optimum sum of these numbers not to exceed a particular number like 1000.
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?
-
- Posts: 862
- Joined: May 05, 2015 5:35
- Location: Germany
Re: Optimum sum of a set of numbers
So welcome back at coding. *smile*
-
- Posts: 2958
- Joined: Jun 02, 2015 16:24
Re: Optimum sum of a set of numbers
Those guys are too fast :)nfunk wrote: Again,
Thank y'all for the prompt help!!!
Nick
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
Good question.grindstone wrote:Thank you. I wonder if there's a more elegant method than brute force.
-
- Posts: 252
- 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"
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.
define "set of numbers"
- the range / any negative numbers
how many
are there duplicates
are they random or ...
- in what range
is it random or ...
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.
Re: Optimum sum of a set of numbers
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.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.
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).
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.
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
-
- Posts: 139
- 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
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
Re: Optimum sum of a set of numbers
Here my version:
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.
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
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.