2009-01-20, 06:19 PM
Ended up looking at Nondeterministic Polynomial-problems, and found this one:
Let X be a finite amount of positive integers. Example:
X = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37}
Is it possible to split X up into two parts Y and Z in such a way that Y = Z?
Well, in the above example, this would be rather easy to state, as the sum of X is an odd number. However, a general algorithm finding this out, what would it consist?
We can easily test out if the outcome number is odd, so that will be the first test. If the sum is odd, then it won't be possible to split X with our requirements.
Next out will be to check if any number in X is over half the sum of X. If it is, then it won't be possible to split X with our requirements.
Next step here would then be to check if i numbers equal to half the sum of X, starting from 1, incrementing by 1 until i is over half of the amount of numbers in X. While we do this, we check if all the solutions are over half the sum of X (if it is, then sorry, no solution).
So, any faster solution than this (or anything else that should be done)?
I'm kinda tired as of right now, but I was thinking about something like checking if all the solutions are under a certain value, but I couldn't get a firm grip on that thought.
Let X be a finite amount of positive integers. Example:
X = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37}
Is it possible to split X up into two parts Y and Z in such a way that Y = Z?
Well, in the above example, this would be rather easy to state, as the sum of X is an odd number. However, a general algorithm finding this out, what would it consist?
We can easily test out if the outcome number is odd, so that will be the first test. If the sum is odd, then it won't be possible to split X with our requirements.
Next out will be to check if any number in X is over half the sum of X. If it is, then it won't be possible to split X with our requirements.
Next step here would then be to check if i numbers equal to half the sum of X, starting from 1, incrementing by 1 until i is over half of the amount of numbers in X. While we do this, we check if all the solutions are over half the sum of X (if it is, then sorry, no solution).
So, any faster solution than this (or anything else that should be done)?
I'm kinda tired as of right now, but I was thinking about something like checking if all the solutions are under a certain value, but I couldn't get a firm grip on that thought.