Python Forum

Hi all.

Wonder anyone here can help to get the algorithm right. I have sorted list of numbers and I need to pair of numbers which add to target or close to target. For instance

List 500 700 1000 1400 2000
target 2300

There inst a direct match but the closest is 1400 + 700 which gives me 2100. And this the right answer.

I've tried the traditional approach were using dynamic programming you the find difference between the current position and the target and look to find the difference number existing in the hash. This works well for a direct match but not for the closet match.

I wonder if there is a better way to doing this?

Any pointers are much appreciated.

Many thanks

(Apr-09-2019, 10:29 PM)hshivaraj Wrote: [ -> ]List 500 700 1000 1400 2000
target 2300

There inst a direct match but the closest is 1400 + 700 which gives me 2100. And this the right answer.

The closet is 1000 + 1400 which gives 2400

items = (500, 700, 1000, 1400, 2000)
target = 2300

from itertools import combinations

nearest = target
best_match = None

for item1, item2 in combinations(items, 2):
    differance = abs(target - (item1 + item2))
    if differance <= nearest:
        best_match = (item1, item2)
        nearest = differance
        
print(f'The best match to {target} is {best_match} at {sum(best_match)}')

Output:
The best match to 2300 is (1000, 1400) at 2400

Unless the best match must be must be equal to or below the target.

items = (500, 700, 1000, 1400, 2000)
target = 2300

from itertools import combinations

nearest = target
best_match = None

for item1, item2 in combinations(items, 2):
    differance = abs(target - (item1 + item2))
    if differance <= nearest and (item1 + item2) <= target:
        best_match = (item1, item2)
        nearest = differance
        
print(f'The best match to {target} is {best_match} at {sum(best_match)}')

Output:
The best match to 2300 is (700, 1400) at 2100

hshivaraj

Yoriz