How to restrict who may read my entries?
Number Comparisons
Hello Guest		   
  • Login
• Register…
• Start blog		   • Who, Where, When
• What can I do?
• What to Read?		   • Polls
• Avatars
• Interests		   • Cities and Countries
• Random blog
• Users search		   • Search
• Games
• Tests
• QAIX		   • Сообщества
• Talxy Chat
• Horoscope
• Online		  
Зарегистрируйся!
QAIX > Java Programming > Number Comparisons 3 October 2000 10:49:00
  Recent blog posts: 
How to make a Christmas photo…
Every Christmas people take a off from their busy schedule. This is the time they can enjoy with their…

Car web design, motorbike…
If you are looking for Car website design, Auto web design, bike web design, or anything similar our…

The Best Video Converter-a…
iOrgSoft Inc. has released the powerful Video Converter - iOrgSoft Video Converter 1.6.0, the latest…

Photo DVD Maker New Website…
AnvSoft Inc., the multimedia software developer, unveils a new website…

How to rip DVD movie, convert…
It is no doubt that PSP is an excellent game player. However, it is not playing games all the time; you…

World’s Most Unusual Christmas…
This Christmas, don’t go with that ho-hum, run-of-the-tree-far­­m tree your family always gets…

Facebook account cracker
facebook account cracker (50 GBP) Before you're told what this tool does, it's worth noting that…

BlackBerry Storm review…
As BlackBerry fans, you can’t miss the BlackBerry Storm. At Nov 6th, 2008, the word on the street is…

Review on Any DVD Cloner
Have you ever had a DVD Movie collection broken or lost? Have you ever wanted to backup movies but…

All recruitment agencys come…
What is RCCSS? RCCSS is a new unique peice of software which will scan millions of major sites and…

  They have birthday today: 
akram mellice
Daffy little vampire
  Forums:   
    topic feeds

• QAIX  all topics, blogs and comments

• PHP web-programming

• Perl web-programming

• ASP web-programming

• Visual Basic Programming

• .Net Development

• C/C++ Programming

• Java Programming

• Javascript web-programming

• Apache HTTP Server

• Web-design

• Web-hosting, dedicated, colocation

• HTML web-programming

• XML development

• General Web-programming

• Content Management Systems

• ColdFusion

• Search Engine Optimization

• Hardware

• Software, Computer Help

• MySQL database development

• PostgreSQL database development

• MS Access database development

• Oracle database development

• MS SQL database development

• Informix database development

• Buy / Sell

• Open discussion

• Anonymous
  Discuss: 
[EJB 3.0] - PersistenceContext…
I have tried to inject a PersistenceContext into a JSF managed bean POJO as is outlined here. The…

[JBoss jBPM] - Re…
Raj, as I just stated in the other thread you will have to lock on processInstance. What seems to be…

Passing LARGE (1500-2500 chars)…
I want to pass a large (easily 1500-2500 characters) variable between a DHTML object using Jscript over…

Rebuild trailer not found…
Hi, in an application that read information from an Oracle database and create a PDF I get this error…
  Recent forum topics: 
Rakudo bug reports still go to…
Some of you may have seen the announcements on the Parrot lists that Parrot will be starting to use…

Stop sql Injection attacks and…
HI there, not long ago I found a website explaining a feature of a dbi-addon (or catalyst-addon) which…

[JCA/JBoss] - getOutputStream()…
Hi Guru, My project was developed by using JDeveloper10g. I have deployed the EAR file to…
  Recent forum comments:
RE: Macro: Substitution font and…
Not a macro approach, but after you have the data in the page you could just use Edit Select All in…

RE: Macro: Substitution font and…
You wouldn't want to use points to size your characters on the web page. Use pixels, em, en, ex…

RE: Problem with uploader
Matthew Whipple wrote: If the open failed then wouldn't the die kick in and at least say something in…

RE: [JCA/JBoss] - getOutputStream()…
Put Your Java Code in Servlet. It will work fine Try to avoid scriplet in jsp

RE: ASP Access Recordset Paging
Thanks a lot! You've been really helpful. What eventually solved the problem was moving the DB from…

RE: ASP Access Recordset Paging
e.l. wrote: You are not using odbc, so you should have removed those groups from the crosspost. I…

RE: ASP Access Recordset Paging
Thanks for the quick reply. 1. I use MS Office Access 2003 (11.8166.8202) SP3 2. The code of my…

RE: ASP Access Recordset Paging
e.l. wrote: We can't answer without seeing: 1. your database type and version 2. your connection string…

RE: ASP Access Recordset Paging
Hi, I'm having a different problem, but the same error message (ADODB.Recordset (0x800A0CB3) ). I…

RE: how to retrieve CheckBox value…
Evertjan. wrote: More like .Count…
  Moderators:
 Administrator
 Protorioris

Number Comparisons

Real GM Webmaster 3 October 2000 10:49:00
 Hi,

I have a problem that has had be scratching my head for the last three weeks.

What I need to do is take a number, say 40, and then have a varying number of other integers that I need to find the best fit into the original number. There could be four, give, or 25 numbers that could fit.

For example, using 40 as the basis.

Just say on the flip side I have 20, 9, 7, 5, and 2.

I need to find the sum of these numbers that will end up closest to 40. In this case the numbers that would be returned would be 20, 9, 7 and 2, which equals 38.. 5 would be left over. Any other sum would either push me over the 40 mark or would fall short of the 38.

Any idea on how to do this. Remember, that the number of numbers that will be compared is not static.

Please help me, because I am completely stuck and this is vital to the accuracy of our site.

Thank you in advance,

Michael.

Add comment
Maxim Maletsky 2 October 2000 15:37:43 [ permanent link ]
 Nice Question, Man....

I've been looking for something similar once and then just gave up replacing
it with some different, less accurate solution, even if in mathematics I am
OK..

Good Luck, man, sorry cannot help you on this, hope you will find here an
answer.


-----Original Message-----
From: Real GM Webmaster [mailto:db7@realgm.com]
Sent: Monday, October 02, 2000 9:28 PM
To: php-general@lists.p­hp.net
Subject: [PHP] Number Comparisons


Hi,

I have a problem that has had be scratching my head for the last three
weeks.

What I need to do is take a number, say 40, and then have a varying number
of other integers that I need to find the best fit into the original number.
There could be four, give, or 25 numbers that could fit.

For example, using 40 as the basis.

Just say on the flip side I have 20, 9, 7, 5, and 2.

I need to find the sum of these numbers that will end up closest to 40. In
this case the numbers that would be returned would be 20, 9, 7 and 2, which
equals 38.. 5 would be left over. Any other sum would either push me over
the 40 mark or would fall short of the 38.

Any idea on how to do this. Remember, that the number of numbers that will
be compared is not static.

Please help me, because I am completely stuck and this is vital to the
accuracy of our site.

Thank you in advance,

Michael.

Add comment
Teodor Cimpoesu 2 October 2000 17:16:43 [ permanent link ]
 Hi Real!
On Mon, 02 Oct 2000, Real GM Webmaster wrote:
Hi,>
I have a problem that has had be scratching my head for the last three weeks.>
What I need to do is take a number, say 40, and then have a varying number of other integers that I need to find the best fit into the original number. There could be four, give, or 25 numbers that could fit.>
For example, using 40 as the basis.>
Just say on the flip side I have 20, 9, 7, 5, and 2.>
I need to find the sum of these numbers that will end up closest to 40. In this case the numbers that would be returned would be 20, 9, 7 and 2, which equals 38.. 5 would be left over. Any other sum would either push me over the 40 mark or would fall short of the 38.>
Any idea on how to do this. Remember, that the number of numbers that will be compared is not static.>
Please help me, because I am completely stuck and this is vital to the accuracy of our site.>
Do you need all the combinations? or just the `longest' as number of
`numbers'?
This pretty looks like a backtracking/greedy­ algo job.

-- teodor
Add comment
Real GM Webmaster 3 October 2000 01:18:02 [ permanent link ]
 ----- Original Message -----
From: "Teodor Cimpoesu" <teo@digiro.net>
To: <php-general@lists.­php.net>
Sent: Monday, October 02, 2000 11:16 PM
Subject: Re: [PHP] Number Comparisons

Hi Real!> On Mon, 02 Oct 2000, Real GM Webmaster wrote:>
Hi,> >
I have a problem that has had be scratching my head for the last three
weeks.> >
What I need to do is take a number, say 40, and then have a varying
number of other integers that I need to find the best fit into the original
number. There could be four, give, or 25 numbers that could fit.> >
For example, using 40 as the basis.> >
Just say on the flip side I have 20, 9, 7, 5, and 2.> >
I need to find the sum of these numbers that will end up closest to 40.
In this case the numbers that would be returned would be 20, 9, 7 and 2,
which equals 38.. 5 would be left over. Any other sum would either push me
over the 40 mark or would fall short of the 38.> >
Any idea on how to do this. Remember, that the number of numbers that
will be compared is not static.> >
Please help me, because I am completely stuck and this is vital to the
accuracy of our site.> >
Do you need all the combinations? or just the `longest' as number of> `numbers'?> This pretty looks like a backtracking/greedy­ algo job.>
-- teodor

I just need the combination of numbers that's sum will give me the closest
number to the original, which in the example is 40. I also need to know
which numbers are left over.

Any ideas?

Thanks again,
Michael


Add comment
Tim Converse 3 October 2000 07:13:20 [ permanent link ]
 This is a hard one -- it's the "subset sum" problem, which is a version of
the "knapsack problem". It is known to be NP-hard, which means that if need
to solve it exactly, for arbitrary integers, then there's no known solution
which is substantially faster than trying all the different possible
combinations.

If you can guarantee a pretty small, fixed, maximum size for your target
number, then the problem becomes easier. Check out the following page, and
search for "subset sum":

http://www.tcs.mu-l­uebeck.de/AlgoDesign­Man/BOOK/BOOK4/NODE1­45.HTM#knapsack

The basic idea is to use an array with as many potential slots as the size
of the target number. You then make a pass over the array for each number
in your set, and on each pass you mark every slot number that has now become
a possible sum. So that you can reconstruct the sum later, we use the
number that made the sum possible as the marker.

For example:

First pass (using 20):

$my_array[20] = 20; // the sum of 20 is .. 20

Second pass (using 9):

$my_array[9] = 9;
$my_array[29] = 9; // the 20 slot plus the current 9

Third pass (using 7):

$my_array[7] = 7;
$my_array[16] = 7;
$my_array[27] = 7;
$my_array[36] = 7; // the 29 slot plus seven (20 + 9 + 7)
(etc.)

When you've used up all the numbers, check the array for the highest marked
slot (having already ruled out slots above the target number). That slot
number is the best you can do. Now to find the sum that made it, just
"unwind" from the top slot. (I.E., to find how you filled the 36th slot,
subtract the 7 you stored there to find the 29th slot, etc ...).

If there's any interest, I'd be happy to code this in PHP and post it.

--tim

On Mon, 2 Oct 2000 22:28:04 +1000, Real GM Webmaster wrote:
Hi,>
I have a problem that has had be scratching my head for the last three
weeks.>
What I need to do is take a number, say 40, and then have a varying
number of other integers that I need to find the best fit into the original
number. There could be four, give, or 25 numbers that could fit.>
For example, using 40 as the basis.>
Just say on the flip side I have 20, 9, 7, 5, and 2.>
I need to find the sum of these numbers that will end up closest to 40.
In this case the numbers that would be returned would be 20, 9, 7 and 2,
which equals 38.. 5 would be left over. Any other sum would either push me
over the 40 mark or would fall short of the 38.>
Any idea on how to do this. Remember, that the number of numbers that
will be compared is not static.>
Please help me, because I am completely stuck and this is vital to the
accuracy of our site.>
Thank you in advance,>
Michael.>





___________________­____________________­________________
Say Bye to Slow Internet!
http://www.home.com­/xinbox/signup.html

Add comment
Tim Converse 3 October 2000 10:49:00 [ permanent link ]
 Here's a PHP function that solves Michael's problem, and it should be pretty
efficient if the numbers involved are small.

The function takes two arguments: an integer maximum, and an array of
integers. It returns an array containing a subset of those integers with
the highest possible sum that is less than or equal to the maximum. (There
may be more than one subset that adds up to that highest sum, and this
function will only return one of them.) See my earlier note below for the
algorithm.

function maximum_subset_sum ($max, $candidate_array) {
$working_array = array();
while ($next = each($candidate_arr­ay)) {
$candidate = $next['value'];
$sums_to_date = array_keys($working­_array);
while ($marked_sum = each($sums_to_date)­) {
$known_sum = $marked_sum['value'];
$possibly_new = $known_sum + $candidate;
if(($possibly_new <= $max) &&
!IsSet($working_arr­ay[$possibly_new])){
$working_array[$possibly_new] = $candidate;
}
}
if(($candidate <= $max) &&
!IsSet($working_arr­ay[$candidate])){
$working_array[$candidate] = $candidate;
}
}
$max_sum = max(array_keys($wor­king_array));
$return_array = array($working_arra­y[$max_sum]);
while ($max_sum != $working_array[$max_sum]) {
$max_sum = $max_sum - $working_array[$max_sum];
array_push($return_­array, $working_array[$max_sum]);
}
return($return_arra­y);
}

// example use
$best_sum = maximum_subset_sum(­40, array(39,23,19,14,9­,5,3,2,1));
print("Largest sum is " . array_pop($best_sum­));
while ($value = array_pop($best_sum­)) {
print(" + $value");
} // will print "Best sum is 23 + 14 + 3"


On Mon, 2 Oct 2000 20:13:20 -0700 (PDT), Tim Converse wrote:
This is a hard one -- it's the "subset sum" problem, which is a version
the "knapsack problem". It is known to be NP-hard, which means that if
need> to solve it exactly, for arbitrary integers, then there's no known
solution> which is substantially faster than trying all the different possible> combinations.>
If you can guarantee a pretty small, fixed, maximum size for your target> number, then the problem becomes easier. Check out the following page,
search for "subset sum":>
http://www.tcs.mu-l­uebeck.de/AlgoDesign­Man/BOOK/BOOK4/NODE1­45.HTM#knapsack>
The basic idea is to use an array with as many potential slots as the
size> of the target number. You then make a pass over the array for each
number> in your set, and on each pass you mark every slot number that has now
become> a possible sum. So that you can reconstruct the sum later, we use the> number that made the sum possible as the marker. >
For example:>
First pass (using 20):>
$my_array[20] = 20; // the sum of 20 is .. 20>
Second pass (using 9):>
$my_array[9] = 9;> $my_array[29] = 9; // the 20 slot plus the current 9>
Third pass (using 7):>
$my_array[7] = 7;> $my_array[16] = 7;> $my_array[27] = 7;> $my_array[36] = 7; // the 29 slot plus seven (20 + 9 + 7)> (etc.)>
When you've used up all the numbers, check the array for the highest
marked> slot (having already ruled out slots above the target number). That slot> number is the best you can do. Now to find the sum that made it, just> "unwind" from the top slot. (I.E., to find how you filled the 36th slot,> subtract the 7 you stored there to find the 29th slot, etc ...). >
If there's any interest, I'd be happy to code this in PHP and post it.>
--tim>
On Mon, 2 Oct 2000 22:28:04 +1000, Real GM Webmaster wrote:>
What I need to do is take a number, say 40, and then have a varying> number of other integers that I need to find the best fit into the
original> number. There could be four, give, or 25 numbers that could fit.> >
For example, using 40 as the basis.> >
Just say on the flip side I have 20, 9, 7, 5, and 2.> >
I need to find the sum of these numbers that will end up closest to
40. > In this case the numbers that would be returned would be 20, 9, 7 and 2,> which equals 38.. 5 would be left over. Any other sum would either push
over the 40 mark or would fall short of the 38.> >
Any idea on how to do this. Remember, that the number of numbers that> will be compared is not static.> >
Please help me, because I am completely stuck and this is vital to the> accuracy of our site.> >
Thank you in advance,> >
Michael.

-------------
How can you support PHP *and* me at the same time?
Order the PHP 4 Bible using http://www.php.net/­books.php. :)­





___________________­____________________­________________
Say Bye to Slow Internet!
http://www.home.com­/xinbox/signup.html

Add comment
 

Add new comment

As:
Login:  Password:  
 
 
  
 
Пожалуйста, относитесь к собеседникам уважительно, не используйте нецензурные слова, не злоупотребляйте заглавными буквами, не публикуйте рекламу и объявления о купле/продаже, а также материалы нарушающие сетевой этикет или УК РФ.

QAIX > Java Programming > Number Comparisons 3 October 2000 10:49:00
see also:
[EJB 3.0] - clustred ejb3 MDB
[Messaging, JMS & JBossMQ] - Re: two…
[JBoss Seam] - Re: Integrating ADF EA19…
пройди тесты:
see also:
Ckoro pjatnica 13.]:-) :-D
I will always be alone...
Hh, it is fast in school. I do not ...
  Copyright © 2001—2008 QAIX
Idea: Miсhael Monashev
Помощь и задать вопросы можно в сообществе support.qaix.com.
Сообщения об ошибках оставляем в сообществе bugs.qaix.com.
Предложения и комментарии пишем в сообществе suggest.qaix.com.
Информация для родителей.
Write us at:
If you would like to report an abuse of our service, such as a spam message, please .