This week's book giveaways are in the Java EE and JavaScript forums.
We're giving away four copies each of The Java EE 7 Tutorial Volume 1 or Volume 2(winners choice) and jQuery UI in Action and have the authors on-line!
See this thread and this one for details.
The moose likes Beginning Java and the fly likes Adding numbers... Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login


Win a copy of The Java EE 7 Tutorial Volume 1 or Volume 2 this week in the Java EE forum
or jQuery UI in Action in the JavaScript forum!
JavaRanch » Java Forums » Java » Beginning Java
Bookmark "Adding numbers..." Watch "Adding numbers..." New topic
Author

Adding numbers...

James Palmer
Ranch Hand

Joined: Mar 15, 2004
Posts: 36
Hello, am making a program and my main problem is that i ve got some numbers(about 20) which are standard values,not changing. I also have a total sum.That total sum is the number that i want to get to.How i get there is that i get 3-4 from the 20 values i have and put out all possible combinations to get to the target number as close as possible using as many digits as needed. The digit combination closer to the total mass target is our wanted combination.For example, if I have the letters P, Y and T, the program would start working out all possible combinations to get to the target number as close as possible using as many digits as needed. The digit combination closer to the total mass target is our wanted combination.We want the sum of the numbers put together.Any idea how this can be done?As i dont know the number of digits i will need this makes the program harder to make(or so i think so).Ideally, you could point to me with what parts of java i would want to do this program and i could learn to do it myself...Thanks a lot for your patience in reading this!
Junilu Lacar
Bartender

Joined: Feb 26, 2001
Posts: 4456
    
    6

Not quite grokking your example--it's just restating the problem. Could you give a more concrete example?


Junilu - [How to Ask Questions] [How to Answer Questions]
James Palmer
Ranch Hand

Joined: Mar 15, 2004
Posts: 36
For example i want to use 3 values,e.g 24, 35 and 55.I want a total value of 290.I would want the computer to make all the calculations needed with all the ways that they could be done using all 3 values or only one of them to find the closest value to 290.One of them could be 24 + 35 + 55 + 24 + 24 + 55 + 35 + 35 = 287. After this the value we get is not as close to 290 as the value we have now.I hope this has made it a bit clearer.Thanks

P.S:The combination i have made is only one of the so many that can be done with those 3 numbers.
[ August 03, 2004: Message edited by: James Palmer ]
Stefan Wagner
Ranch Hand

Joined: Jun 02, 2003
Posts: 1923

Assuming x is the target-value.
Assuming x, a, b, ... > 0.

Since a + b = b + a, you may start to order your variables first by size.

Assuming they are already ordered, and a is the smallest value.
Your 'best match' has to be greater than (x-a).
Else, adding 'a' would make a better result.

Adding 'a' is generally a good idea, if the current result is < (x- (a/2).



So sum > x-(a/2) && sum < x + (a/2) is a nice stop-condition.

If you build your sums in a way, that:
s1 + s2 + s3 + ... + si + ... +sn = sum
with s1 <= s2 <= ... s(i-1) <= si <= s(i+1) <= .... <= sn,
you may prevent building the same sum multiple times.
If you have all best combinations, you can build all permutations for that expression.

Sounds like that backpacking problem, which is NF-complete...


http://home.arcor.de/hirnstrom/bewerbung
Vijay Vaddem
Ranch Hand

Joined: Feb 13, 2004
Posts: 243
Hi Stefan,

What is the value of 'i' in the above code?? could u elaborate on your
explanation?

thanks,

Vijay
Stefan Wagner
Ranch Hand

Joined: Jun 02, 2003
Posts: 1923

I used i two times, not related to each other.
First usage:


x is the target sum.
a is the smallest number in the ensemble.
i is the distance of a temporary, close to optimal sum from x

If you know the target is 913, and the smallest number is 7.
Without dividing 913/7 you may say, that 913 - 7 can't be the best value,
because you could add another 7 that value, and reach 913 exact.
But if you only may produce (913-7) + 1 = 907 ?
You could add 7 too, and reach 914, which is closer to 913 than 907.
This is true for for 908, 909 but not for 910.
909 + 7 = 916
913 - 909 = i = 4
916 - 913 = i = 3 better

910 + 7 = 917
913 - 910 = 3 (=i) better
917 - 913 = 4 (=i)

s(i):

Only a helping variable, maybe an arrayindex.
I should have called it j.

If the sum shall be 49.
I would start with j=0, s(j)=s(0)=2
4 + 4 + 4 + ... + 4 = 48
+ 4 = 54
8 is closer to 49 than 54, we choose 48 as primary suboptimal value.

Now I add the next greater value than 4, increase j, s(j=1)=5.
4 + 4 + ....+ 5 = 53
48 + 5 is 53 which is too big (i=4).
Now we remove '+ 4' until we hit 49 or get lower than 48.
Hm.
53 - 4 = 49 - target hit. Example too simple.
But perhaps you got the idea now.
 
I agree. Here's the link: http://aspose.com/file-tools
 
subject: Adding numbers...