|
|||||||||
|
|||||||||
| |||||||||
|
|||||||||
|
|||||||||
| |||||||||
|
|
|
| |||||||||
 |
|
|
«
Previous Thread
|
Next Thread
»
|
Thread Tools | Search this Thread | Rate Thread | Display Modes |
Dev Shed Forums Sponsor:
|
|
|
|
#1
December 14th, 2004, 01:44 PM
|
|||
|
|||
|
closest sum algorithm.
I am studying for an algorithms final and i'm having trouble with some of the review questions.
2 in particular deal with the same idea. 2. Let A[1, ..., n] be an array of n numbers (some positive and some negative. (a)Give an algorithm to find which two numbers have sum closest to zero. Make your algorithm as efficient as possible. Write it in pseudo code. (b)Analyze its running time. The second question is the same but it is finding the three numbers with a sum closest to zero. I can't figure out a much better way to do this than by brute force. I also looked around the net and it seems this may be an NP-complete problem. Any ideas you have would be greatly appreciated. Thanks
|
|
#2
December 14th, 2004, 07:43 PM
|
|||
|
|||
|
For the first question, the obvious answer is to compare every element with every other, for an O(N^2) algorithm. However a better way is this:
1) sort the array 2) find the two elements either side of zero (if they are all +ve or all -ve then the answer is trivial) 3) add the two values at those positions. If the total is +ve then increment the -ve index, if it is -ve then increment the +ve index. If it is zero then stop. 4) loop step (3) until you hit a zero total or run off the end of the array. Store your best total as you go. Here is a working implementation in Python (the closest thing to executable pseudocode there is) : Code:
import random
#create a random list of 10 values from the range -100 to +100
lst = random.sample(xrange(-100,101), 10)
lst.sort()
#find the first value greater than zero
for hi, val in enumerate(lst):
if val > 0:
break
if hi == 0:
hi = 1
lo = hi-1
best = abs(lst[lo]+lst[hi])
bestIdx = (lo, hi)
while lo >= 0 and hi < len(lst):
current = lst[lo] + lst[hi]
print "testing", lo, lst[lo], hi, lst[hi], current, best
if abs(current) < best:
best = abs(current)
bestIdx = (lo, hi)
if current == 0:
break
if current > 0:
lo -= 1
else:
hi += 1
print lst
print "best = ", best, "indexes =", bestIdx
The runtime is O(N log(N)), since the dominant factor is sorting the list. The actual scanning is O(N). Extending this to the sum of 3 values is left as an exercise for the reader. (meaning I don't know the answer  )Dave - The Developers' Coach
|
|
#3
December 14th, 2004, 07:48 PM
|
|||
|
|||
|
To prove it works, here is some sample output:
testing 6 -8 7 23 15 15 testing 5 -13 7 23 10 15 testing 4 -56 7 23 -33 10 testing 4 -56 8 77 21 10 testing 3 -59 8 77 18 10 testing 2 -70 8 77 7 10 testing 1 -88 8 77 -11 7 testing 1 -88 9 78 -10 7 [-94, -88, -70, -59, -56, -13, -8, 23, 77, 78] best = 7 indexes = (2, 8) testing 5 -37 6 7 -30 30 testing 5 -37 7 36 -1 30 testing 5 -37 8 40 3 1 testing 4 -58 8 40 -18 1 testing 4 -58 9 52 -6 1 [-99, -81, -76, -64, -58, -37, 7, 36, 40, 52] best = 1 indexes = (5, 7) testing 6 -35 7 9 -26 26 testing 6 -35 8 14 -21 26 testing 6 -35 9 28 -7 21 [-89, -81, -59, -55, -43, -36, -35, 9, 14, 28] best = 7 indexes = (6, 9) Dave - The Developers' Coach
|
|
| Viewing: Dev Shed Forums > Programming Languages - More > Software Design > closest sum algorithm. |
| Thread Tools | Search this Thread |
| Display Modes | Rate This Thread |
|
|
 |
|
|
Del.icio.us
Digg
Google
Spurl
Blink
Furl
Simpy
Y! MyWeb
Linear Mode
