2

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.

max5336
  • 39
  • 5

2 Answers2

2

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.

ADdV
  • 1,162
  • 2
  • 16
0

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
IoaTzimas
  • 10,538
  • 2
  • 13
  • 30
  • thank you. I try to understand the way you did. What is "itertools.combinations" ? – max5336 Sep 22 '20 at 16:45
  • ok I got it ! But in the line "for k in itertools.combinations(my_list, i):" it should be "i+1" no ? – max5336 Sep 22 '20 at 16:58
  • It's a function that returns all combinations of a list. Check here: https://stackoverflow.com/questions/17053070/making-combinations-python – IoaTzimas Sep 22 '20 at 16:59
  • Yes you are right, i changed the code so that it will loop over 1 to len(my_list) (included) – IoaTzimas Sep 22 '20 at 17:01
  • 1
    Ok thank you ! I I try to find out the complexity of combinations to get the total complexity of this algorithm. – max5336 Sep 22 '20 at 17:03
  • @max5336 This code brute forces over every possible subset of the n given numbers, so it will have exponential complexity O(2**n). – ADdV Sep 22 '20 at 18:51