This message was edited by the acaramarin at 2002-6-30 23:32:19
Hi,
Finally I managed to solve the problem using an algorithm whose name is "brute force" meaning that I have to generate all the possible combinations between the numbers from the crowd. I don't think this problem can be solved other way.
My e-mail is acaramarin@hotmail.com. If you want, I can send you my final solution, which is coded in Java.
Thanks a lot for your help,
Adrian
: Hi
:
: I thought your problem was interesting so I created a program to test out my algorithm in Delphi. The program works with the sample values you provided. I just didn't sort them so they are out of order. Because I don't know what algorithm you are using, I don't know if mine is actually an improvement. I'd like to have your email address so I can email you the source code. It would probably be very helpful to you if you don't understand my explanation.
:
: Here is my explanation. I hope it makes some sence to you.
:
:
variables:
:
: I used two stacks. 1 stored the sequence and was created once for a particular limit and sequence while the second one was modified to get the numbers out of the sequence without using the same number twice. After each check the first stack was copied into the second stack.
:
: I stored the limit and the combination number globally.
:
:
procedures:
:
: To use the stacks, which are arrays of integer, as stacks, I created push and pop procedures. The pop took as a parameter the index in the stack, returned that value and also copied the integer at the end of the stack into it.
: I also used a factorial function in the calculation of the number of possible combinations and in the calculation of each index in the stack to find a .
:
: The main procedure loops through all combinations for the sequence. The number of posible combinations is equal to the Factorial(number of numbers in the sequence). For each check for the near sum to the limit, I changed the combination number variable and called the function below. I used variables to store the combination number that provided the nearest sum to the limit. After the loop was complete, I outputted the sequence to an edit box by finding the same numbers from the sequence as the function below, separated by commas.
:
: Here is the checking function:
:
:
:
: function NearestWithCombo: integer;
: // return the nearest value to the limit
: var
: sum1: integer; // the sum of the pushed data
: v: integer;
: hs: integer; // used to store the size of the stack
: tcombo: integer; // a value that is manipulated
: begin
: CopyMainStack; // copy the information from mainstack1 into stack1
: sum1:=0;
: hs:=high(stack1);
: tcombo:=ComboNumber;
: while (0<hs)and(sum1<=limit) do
: begin
: v:=tcombo div Factorial(hs-1);
: tcombo:=tcombo-v;
: v:=pop(tcombo);
: sum1:=sum1+v; // pop a value from the stack and add it to the sum
: dec(hs); // subtract 1 from hs
: end;
: result:=limit-sum1;
: end;
:
:
:
:
: The reason the factorial function was used in the code was because the number of combinations remaining are devided by the length of the stack each time.
:
: I hope this helps.
:
:
:
: : Hello people,
: :
: : I have a problem which is bothering me. It is not necessary a Java problem, it is a problem of finding an algorithm which does the right work.
: : The problem is: I have a multitude of numbers ( doubles ) and a limit that is also a double. I want to obtain a sequence of numbers, from those crowd ( multitude ) whose sum is the closest to the limit. I'll make an example to be more clear;
: :
: : Ex1. 40,7,4,4 and 50 the limit => the best solution [40,4,4] is 48 = 40 + 4 + 4 the nearest number close to the limit
: : Ex2. 30,20,15,15,15,15 and 90 the limit => solution [30,15,15,15,15]
: :
: : Thanks in advance
: : Adrian
: :
:
:
