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

- 141.3K All Categories
- 104.5K Programming Languages
- 6.4K Assembler Developer
- 1.9K Basic
- 39.8K C and C++
- 4.3K C#
- 7.9K Delphi and Kylix
- 4 Haskell
- 9.6K Java
- 4.1K Pascal
- 1.3K Perl
- 2K PHP
- 513 Python
- 48 Ruby
- 4.3K VB.NET
- 1.6K VBA
- 20.8K Visual Basic
- 2.6K Game programming
- 311 Console programming
- 89 DirectX Game dev
- 1 Minecraft
- 110 Newbie Game Programmers
- 2 Oculus Rift
- 8.9K Applications
- 1.8K Computer Graphics
- 729 Computer Hardware
- 3.4K Database & SQL
- 522 Electronics development
- 1.6K Matlab
- 628 Sound & Music
- 256 XML Development
- 3.3K Classifieds
- 195 Co-operative Projects
- 182 For sale
- 189 FreeLance Software City
- 1.9K Jobs Available
- 600 Jobs Wanted
- 201 Wanted
- 2.9K Microsoft .NET
- 1.7K ASP.NET
- 1.1K .NET General
- 3.2K Miscellaneous
- 4 Join the Team
- 0 User Profiles
- 349 Comments on this site
- 59 Computer Emulators
- 2K General programming
- 178 New programming languages
- 610 Off topic board
- 167 Mobile & Wireless
- 41 Android
- 124 Palm Pilot
- 335 Multimedia
- 151 Demo programming
- 184 MP3 programming
- 0 Bash scripts
- 19 Cloud Computing
- 53 FreeBSD
- 1.7K LINUX programming
- 367 MS-DOS
- 0 Shell scripting
- 320 Windows CE & Pocket PC
- 4.1K Windows programming
- 888 Software Development
- 405 Algorithms
- 68 Object Orientation
- 87 Project Management
- 90 Quality & Testing
- 237 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
- 34 JQuery
- 283 WEB Servers
- 149 WEB-Services / SOAP

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

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-2015 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.

675MemberI 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

:

6MemberHi,

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 [email protected] 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

: :

:

: