Find the best approximation of a subset for a value

user_11248025 0
Viewed 299

I would like to get an algorithm that gives me the best approximation for a value based on subset.

Here is an example:

N = 45

subset = [25,10,65,9,8]

output: [25,10,9]

The important point is that the algorithm must give the best approximation (regardless the number of the element in the final result). The result must provide the association that gives the exact value of the nearest (but can not exceed the initial value).

Do you know an algorithm that could do that with the minimal time cost ?

Thanks a lot for you help.

nearest-neighbor algorithm python
2 Answers

You cannot to do so in polynomial time (unless P=NP)

Finding out if there is a subset with sum exactly N is clearly easier than finding the subset with sum closest to N, and this former problem is called subset-sum which is known to be NP-complete.

However, pseudo-polynomial time is possible. In fact, your problem is exactly equal to the 0/1 knapsack optimization problem if we take the values in subset to be both the values in weights for the translation to knapsack. This 0/1 knapsack problem has a dynamic programming solution that runs in O(nW) where n is the number of items in subset and W is the target, which is N in your code.

user_143177340

The following code works for short lists. However performance will reduce significantly for longer lists:

import itertools
def closest(my_list, my_number):
    l=[]
    for i in range(1,len(my_list)+1):
        for k in itertools.combinations(my_list, i):
            l.append([k, sum(k)])
    l=[i for i in l if i[1]<=my_number]
    l.sort(key=lambda x:x[1])
    return l[-1]
print(closest(subset, 45)[0], closest(subset, 45)[1])

Output:

(25, 10, 9) 44
user_82285580
Related