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

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

- 140.8K All Categories
- 103.6K Programming Languages
- 6.4K Assembler Developer
- 401 Assembly Code Share
- 239 Getting started in assembly
- 4.6K x86 Assembly
- 1.9K Basic
- 97 Qbasic
- 39.9K C and C++
- 5.6K Beginner C/C++
- 330 C/C++ on Linux/Unix
- 450 C/C++ Windows API
- 522 C++ Builder
- 253 C++ Game Development
- 3.3K C++ MFC
- 103 C++.NET
- 404 Visual C++
- 2.9K C#
- 7.9K Delphi and Kylix
- 334 Advanced Delphi
- 360 Delphi beginners
- 4 Haskell
- 9.7K Java
- 56 Enterprise JavaBeans
- 1.3K Java Beginners
- 304 Java Server Pages
- 4.1K Pascal
- 1.3K Perl
- 11 Perl 6
- 2K PHP
- 546 Python
- 37 Ruby
- 4.4K VB.NET
- 258 Advanced VB.Net
- 1.6K VBA
- 20.8K Visual Basic
- 767 Access databases and VB
- 831 Advance Visual Basic
- 1.2K Beginner VB
- 2.6K Game programming
- 315 Console programming
- 90 DirectX Game dev
- 1 Minecraft
- 112 Newbie Game Programmers
- 2 Oculus Rift
- 9K Applications
- 1.8K Computer Graphics
- 279 3D Graphics
- 129 DirectX
- 125 OpenGL
- 740 Computer Hardware
- 9 Cooling & Overclocking
- 3.4K Database & SQL
- 1.1K Access
- 91 ADO Programming
- 288 MySQL
- 358 Oracle
- 440 SQL-Server
- 535 Electronics development
- 1.6K Matlab
- 628 Sound & Music
- 25 DirectSound
- 257 XML Development
- 3.3K Classifieds
- 199 Co-operative Projects
- 198 For sale
- 190 FreeLance Software City
- 1.9K Jobs Available
- 603 Jobs Wanted
- 209 Wanted
- 2.9K Microsoft .NET
- 1.8K ASP.NET
- 1.1K .NET General
- 22 .NET WEB-Services
- 129 .NET WinForms
- 14 .NET XML
- 50 ADO.NET
- 142 C# & VB.NET School Support
- 3.4K Miscellaneous
- 4 Join the Team
- 354 Comments on this site
- 69 Computer Emulators
- 2.1K General programming
- 187 New programming languages
- 621 Off topic board
- 200 Mobile & Wireless
- 72 Android
- 126 Palm Pilot
- 338 Multimedia
- 154 Demo programming
- 184 MP3 programming
- 0 Bash scripts
- 27 Cloud Computing
- 1 Witsbits Go Cloud
- 53 FreeBSD
- 1.7K LINUX programming
- 1 Awk scripting
- 332 Linux Support
- 0 Sed scripting
- 370 MS-DOS
- 0 Shell scripting
- 321 Windows CE & Pocket PC
- 4.1K Windows programming
- 177 COM/DCOM
- 61 Networking And Security
- 17 Windows 2003 Server
- 6 Windows Vista
- 176 Windows XP
- 939 Software Development
- 416 Algorithms
- 68 Object Orientation
- 24 RUP & UML
- 91 Project Management
- 95 Quality & Testing
- 268 Security
- 63 Evil Scripting
- 81 Hacking
- 7.7K WEB-Development
- 1.8K Active Server Pages
- 61 AJAX
- 4 Bootstrap Themes
- 55 CGI Development
- 28 ColdFusion
- 224 Flash development
- 1.4K HTML & WEB-Design
- 1.4K Internet Development
- 131 Mobile Internet & Messaging
- 211 Wireless development
- 2.2K JavaScript
- 37 JQuery
- 304 WEB Servers
- 153 Apache
- 79 IIS
- 150 WEB-Services / SOAP

## Comments

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.

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

:

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

: :

:

: