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

- 140.4K All Categories
- 104.3K Programming Languages
- 6.3K Assembler Developer
- 1.8K Basic
- 39.7K C and C++
- 4.2K C#
- 7.9K Delphi and Kylix
- 4 Haskell
- 9.6K Java
- 4.1K Pascal
- 1.3K Perl
- 1.9K PHP
- 503 Python
- 47 Ruby
- 4.3K VB.NET
- 1.6K VBA
- 20.8K Visual Basic
- 2.6K Game programming
- 308 Console programming
- 88 DirectX Game dev
- 1 Minecraft
- 108 Newbie Game Programmers
- 2 Oculus Rift
- 8.9K Applications
- 1.8K Computer Graphics
- 726 Computer Hardware
- 3.4K Database & SQL
- 520 Electronics development
- 1.6K Matlab
- 627 Sound & Music
- 254 XML Development
- 3.2K Classifieds
- 189 Co-operative Projects
- 171 For sale
- 189 FreeLance Software City
- 1.9K Jobs Available
- 598 Jobs Wanted
- 199 Wanted
- 2.9K Microsoft .NET
- 1.7K ASP.NET
- 1.1K .NET General
- 2.9K Miscellaneous
- 3 Join the Team
- 2 User Profiles
- 352 Comments on this site
- 56 Computer Emulators
- 1.7K General programming
- 136 New programming languages
- 598 Off topic board
- 159 Mobile & Wireless
- 33 Android
- 124 Palm Pilot
- 334 Multimedia
- 151 Demo programming
- 183 MP3 programming
- 0 Bash scripts
- 15 Cloud Computing
- 52 FreeBSD
- 1.7K LINUX programming
- 364 MS-DOS
- 0 Shell scripting
- 318 Windows CE & Pocket PC
- 4.1K Windows programming
- 877 Software Development
- 401 Algorithms
- 67 Object Orientation
- 82 Project Management
- 88 Quality & Testing
- 232 Security
- 7.5K WEB-Development
- 1.8K Active Server Pages
- 61 AJAX
- 2 Bootstrap Themes
- 55 CGI Development
- 19 ColdFusion
- 222 Flash development
- 1.4K HTML & WEB-Design
- 1.4K Internet Development
- 2.2K JavaScript
- 33 JQuery
- 282 WEB Servers
- 107 WEB-Services / SOAP

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.

acaramarin
Posts: **6**Member

in Algorithms

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

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

About & Contact / Terms of use / Privacy statement / Publisher: Lars Hagelin

Programmers Heaven articles / Programmers Heaven files / Programmers Heaven uploaded content / Programmers Heaven C Sharp ebook / Operated by CommunityHeaven LLC

© 1997-2013 Programmersheaven.com - All rights reserved.

## Comments

27MemberAnyway 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.

- Spam

0 · Vote Down Vote Up · Share on Facebook675MemberI 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

:

- Spam

0 · Vote Down Vote Up · Share on Facebook6MemberHi,

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

: :

:

:

- Spam

0 · Vote Down Vote Up · Share on Facebook