Prev: Another approach to Decide Solvability of Univariate Integer Polynomials, and a possible Multivariate Extension
Next: How can I tell if F is a string or if it is a number?
From: HorkGames on 4 Apr 2008 17:03
So I was thinking about the subset sum problem and the case where the
subset is bounded to only two numbers. This case is obviously not np-
complete. Anyway for the fastest way to solve this specific case is
something I want to know. I'm unsure if there are any books that
delve into it but I know on the internet there are some examples.

For instance when asked to see if Z is in the subset of a set K with N
numbers first sort the set and find the largest/smallest number and
compare this with Z. IF it is greater, then increase the smaller
number, if it is less then decrease the largest number until you
exhaust all numbers.

Assuming the set is sorted this should only take O(n) time (correct me
if wrong).


Another way I was messing around with was to create two arrays filled
with the sorted set of numbers. Start by creating two counters set at
the midpoint of each array and test with a <, >, = test. At each test
create rule(s) for further tests. For instance the first test is
greater then. Then the rule created is (if OtherCounter is <=
midpoint, newLow = midpoint). There is only one rule created due to
symmetry, but in most cases two rules will be created. Then one of
the counters is moved to a new midpoint based on his current relation
to the rules. So for instance CounterA will be moved to a point 3/4
into the array since that is the midpoint between midpoint and
highpoint.

Each movement is switched between the two arrays. So they move in a
walking pattern, one then the other. After each step the comparison
takes place, new rules are created, movement is passed to the next
counter which calculates newLow, and newHigh.

Yeah anyway I just do this for fun so excuse the lack of proper
terminology etc. Does anyone know a good document on this or
anything? I'm an amateur but for some reason there is something very
interesting to me about complexity theory and algorithms.



 | 
Pages: 1
Prev: Another approach to Decide Solvability of Univariate Integer Polynomials, and a possible Multivariate Extension
Next: How can I tell if F is a string or if it is a number?