Howdy, Stranger!

It looks like you're new here. If you want to get involved, click one of these buttons!

Categories

Welcome to the new platform of Programmer's Heaven! We apologize for the inconvenience caused, if you visited us from a broken link of the previous version. The main reason to move to a new platform is to provide more effective and collaborative experience to you all. Please feel free to experience the new platform and use its exciting features. Contact us for any issue that you need to get clarified. We are more than happy to help you.

Programming problem, I couldn't get the best solution

acaramarinacaramarin Posts: 6Member
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

Comments

  • Karl007Karl007 Posts: 27Member
    Real numbers or integers ?

    Anyway if the pb is just get the solution. You have to test any possible set (any size from 1 to N) and sum it. Keep the lower nearest of all these possible sets. That's really unefficient if N becomes bigger but else it's complex and I cant see an obvious optimisation.
  • Josh CodeJosh Code Posts: 675Member
    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.

    [b]variables:[/b]

    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.

    [b]procedures:[/b]

    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:

    [code]

    [b]function[/b] NearestWithCombo: integer;
    // return the nearest value to the limit
    [b]var[/b]
    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
    [b]begin[/b]
    CopyMainStack; // copy the information from mainstack1 into stack1
    sum1:=0;
    hs:=high(stack1);
    tcombo:=ComboNumber;
    [b]while[/b] (0 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
    :

  • acaramarinacaramarin Posts: 6Member
    [b][red]This message was edited by the acaramarin at 2002-6-30 23:32:19[/red][/b][hr]
    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.
    :
    : [b]variables:[/b]
    :
    : 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.
    :
    : [b]procedures:[/b]
    :
    : 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:
    :
    : [code]
    :
    : [b]function[/b] NearestWithCombo: integer;
    : // return the nearest value to the limit
    : [b]var[/b]
    : 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
    : [b]begin[/b]
    : CopyMainStack; // copy the information from mainstack1 into stack1
    : sum1:=0;
    : hs:=high(stack1);
    : tcombo:=ComboNumber;
    : [b]while[/b] (0 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
    : :
    :
    :







Sign In or Register to comment.