James Palmer

Ranch Hand

Posts: 36

posted 13 years ago

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!

posted 13 years ago

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

*Practice only makes habit, only perfect practice makes perfect.
Practice mindfully by doing the right things and doing things right.*— Junilu

[How to Ask Questions] [How to Answer Questions]

James Palmer

Ranch Hand

Posts: 36

posted 13 years ago

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 ]

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 ]

posted 13 years ago

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

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

Vijay Vaddem

Ranch Hand

Posts: 243

posted 13 years ago

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.

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.