Here is a tricky question that I don't know if it has an answer or not.
If you are given N floating point numbers all between 0..1 adding up to an integer.
e.g.
then question is this:
"Decide whether any subset of these numbers adds up to an intger." In this case the answer is:
{ 0.12345, 0.6789, 0.19765 } Total = 1.0
or
{ 0.31415, 0.68585 } Total = 1.0
Obviously one way of doing this is to simply try out every posible subset. The time this takes will grow exponentially in terms of the number of floats you start with. I wonder if there is a quicker trick to doing this. (Or alternatively if there is a way to prove that there isn't a quicker way of doing it.)
For example maybe there is a way to make approximate guesses and then refine them. Or someway of discounting certain subsets so you don't have to check them all?
P.S. Maybe you can guess why I wanted to know the answer to this?
The first solution that came into my head was to sort the list and move an iterator foward and an iterator backwards, adding the two numbers until 1 is reached or exceeded. Unfortunatly this wouldn't work for "any integer" (just for 1.0) or for more than 2 numbers at once.
Because of the requirement for "any integer" and because it can be formed by any combination of any number of numbers, it leads me to believe that there is no solution that dosn't involve comming up with all the combinations of available numbers anyway.
Unless you can come up with some kind of clever, n-dimentional partitioning deal that may or may not work [smile].
I would be interested to know what this is for. Particularly because knowing the context may lead to better solutions probably involving different data structures or a slow solution that can be cached.
Also - what about re-use of the numbers? Can we reuse a number in two combinations? This could lead to some unexpected results if your vector was full of integers anyway.
You'll probably have to try a large number of subsets by brute force, but you might be able to speed things up a bit. For example, first find the sum of the entire set: 2. In this case, none of the subsets will add up to any integer higher than 2. This will explode in a huge ball of flame if you introduce negative numbers, so I assume we only have positive input values for now.
For each entry in the list, track the difference between the entry and each integer up to the max. The first entry has 2 - 0.68585 = 1.31415 and 1 - 0.68585 = 0.31415. Since both of these results are positive, the entry can be used in subsets adding up to 1 and 2. For each integer (in this case, 1 and 2) store a list of the entries that can appear in a subset which totals up to that number. The max total (2 in this case) should have each entry in the original list.
Now you can simply look at each integer up to the max, and you only need to bother trying to build subsets out of those entries which can possibly add up to the integer in question. Obviously this only helps you if your input is distributed over the interval [0, max integer]. Within each grouping, you can also probably sort the list in descending order, and exclude pairs that total more than the search parameter. For instance, in the grouping for 1, 0.68685 will appear next to 0.6789, but obviously these two will never appear in the same subset totalling to 1. This should probably cut down the number of subsets you have to try by a large factor. I have half an inkling of a more powerful trick just under the surface here, but I'm too distracted to properly think it out at the moment.
Anyways, this should help a bit with very long lists, but will probably be a net slowdown in short lists (off the top of my head, say, 15 elements).
[edit] My thoughts continue to try to form here [smile] Using the difference you calculated in the early step (2 - 0.68585 = 1.31415, 1 - 0.68585 = 0.31415) you can also exclude even more subsets. Suppose I have a subset S that totals 1.4. If I am considering adding 0.68685 to this subset to total 2, I can check and see that 1.4 > 1.31415, and I do not need to consider the set {0.68585, {A}}. However, I'm not sure if this could lead to something actually useful, or if it's just a goofy half-optimization that could be done by checking if (0.68585 + 1.4 > 2)... err... exercise to the reader [wink]
The context is of taking the real roots of a polynomial (x-x0)(x-x1)(x-x2).. and of seeing if any combination of the factors gives integer coefficients by first seeing if any of the sums of the real numbers give integers. But we only need to consider the fractional part of the reals numbers.
Even though this is the context please ignore it because I think the puzzle is interesting in itself.
So you can't use any number twice, and only one subset is needed to be found.
[edit] Thats right, ApochPiQ, I hadn't thought of that. For example if I was looking for 3 numbers that add up to an integer, I know that that integer must be 1 for a start. Then if any two numbers add up to more than one I can discount them straight away without adding a third number to it.
So that is indeed an optomization. I wonder if that kind of thing would still work if all the starting numbers were quite small? That's opened up a can of worms if ever I saw one.
[Edited by - paulbird on July 1, 2005 10:07:06 AM]
Reminds me of the knapsack problem, which is NP-complete if I'm not mistaken, meaning that if you can solve it in polynomial time, you've just broken most of the cryptographic systems in the world.
SamLowry - well I'm not one to duck away from a challenge!
But I think this problem may have a simpler solution since it is related, in a way, to factoring integer polynomials for which (so I believe) a polynomial time algroithm exists. Although, admittedly, this would require extra constraints on the numbers such that (x-x0)(x-x1)(x-x2) formed a polynomial with integer coefficients.
It is like the knapsack problem (it is like many OR and CO problems), but not quite. The problem is that there is nothing to minimize or maximize contiuously: whether something is an integer or not is not a property that can be described by a linear constraint of the appropriate form, rendering most common approaches such as linear programming or branch-and-bound variants unuseable.
Your actually getting closer to the knapsack problem. Which in case you're unfamiliar with it is: given a set of integers S and a (integer) goal G, which integers from S do you need to add together to get G? Example: S = {1,6,8,14,29,31}, G = 53 => 8 + 14 + 31.
If you would take the logarithm of each Zn (Un = ln Zn) you need to find a sum again which amounts to 0. You can simplify Un = 2 * Pi * I * Xn, which you can simplify to just Un = Xn mod 1.0 (and still need to get to 0).
In any case, you can transform the problem all you want, it'll remain hard. However, there are special kinds inputs for which it's easy to find a solution (in polynomial time). In fact, there are so many such special/easy cases that a cryptographic encoding system based on the NP-ness of the knapsack problem was considered very unsafe (Merkle Hellman).
For example, it's easy to solve S = {1536, 768, 384, 192, 96, 48, 24, 12, 6, 3, 1}, G = 1008.
if you were going to go about it the brute force way you could easily cut the checking down by half if you counted through the array first to see how many numbers you have and created 2 new dynamic arrays. one that has only the numbers from 0 - 0.5 and the one that contains the numbers > 0.5 && < 1.0.
then you could check from one array1 to array2 since any 2 numbers from the same array would never add up to an integer, assuming that you will never have numbers exactly 0 or exactly 1 which i gather is correct.
if you had 2 million numbers then obviously any brute force way would be slow i just was throwing out an alternative to it.
