This week's book giveaway is in the Design forum.We're giving away four copies of Design for the Mind and have Victor S. Yocco on-line!See this thread for details.
Win a copy of Design for the Mind this week in the Design forum!

James Palmer
Ranch Hand
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
Posts: 7465
50
Not quite grokking your example--it's just restating the problem. Could you give a more concrete example?

James Palmer
Ranch Hand
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
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...

Ranch Hand
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
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.
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.