Finding Combination Of Numbers That Sum Closest To A Target

So I have a combination of floats and I also have a few target values and I want to see if any combination of those floats (allowing duplicates) can sum as close as possible to the

Solution 1:

The easiest way to approach this is to iterate through all combinations of your numbers and keep track of which combination is the closest at the current time

import math
import itertools

numbers = [1,2,3,4]
target = 9
best_combination = ((None,))
best_result = math.inf
best_sum = 0print("target:{}\nnumbers:{}".format(target,numbers))
# generate all combinations of the numbers# including combinations with different lengthsfor L inrange(0, len(numbers)+1):
    for combination in itertools.combinations(numbers, L):
        sum = 0for number in combination:
            sum += number
        result = target - sumifabs(result) < abs(best_result):
            best_result = result
            best_combination = combination
            best_sum = sumprint("\nnew best\n{}\nsum:{} off by:{}".format(best_combination, best_sum, best_result))

print("\nbest sum{} = {}".format(best_combination, best_sum))

Output

target:9numbers:[1, 2, 3, 4]

new best
()
sum:0offby:9new best
(1,)
sum:1offby:8new best
(2,)
sum:2offby:7new best
(3,)
sum:3offby:6new best
(4,)
sum:4offby:5new best
(1, 4)
sum:5offby:4new best
(2, 4)
sum:6offby:3new best
(3, 4)
sum:7offby:2new best
(1, 3, 4)
sum:8offby:1new best
(2, 3, 4)
sum:9offby:0

best sum(2, 3, 4) = 9

If the result at the end is too far off you can disqualify it at the end, or you can set the best result to what you want to be the cut off to be at the beginning.

So change best_result = math.inf to best_result = 0.5 if you want the result to be closer than 0.5 to the given target. The output of that (for input [1,2,3] and target 9) would be

target:9numbers:[1, 2, 3]
best sum(None,) = 0.5

This is not the most efficient way to do this. There are ways to make short cuts, but this is the one of the easiest first approaches.

Edit, to allow duplicates I first generate a list with the maximum number of each number included so for your example it includes the maximum number of 13.02s and 16.08s and...

import math
import itertools

target = 134
numbers = [13.02, 16.08, 100.01, 44.63]
n = len(numbers)
long_list_numbers = []
for number in numbers:
    long_list_numbers += ([number] * int(target / number))


best_combination = ((None,))
best_result = math.inf
best_sum = 0print("target:{}\nnumbers:{}".format(target,numbers))

# generate all combinations of the numbers# including combinations with different lengthsfor L inrange(0, len(long_list_numbers)+1):
    for combination in itertools.combinations(long_list_numbers, L):
        sum = 0for number in combination:
            sum += number
        result = target - sumifabs(result) < abs(best_result):
            best_result = result
            best_combination = combination
            best_sum = sumprint("\nnew best\n{}\nsum:{} off by:{}".format(best_combination, best_sum, best_result))

print("\nbest sum{} = {}".format(best_combination, best_sum))

Output

target:134numbers:[13.02, 16.08, 100.01, 44.63]

new best
()
sum:0offby:134new best
(13.02,)
sum:13.02offby:120.98new best
(16.08,)
sum:16.08offby:117.92new best
(100.01,)
sum:100.01offby:33.989999999999995new best
(13.02, 100.01)
sum:113.03offby:20.97new best
(16.08, 100.01)
sum:116.09offby:17.909999999999997new best
(100.01, 44.63)
sum:144.64000000000001offby:-10.640000000000015new best
(13.02, 13.02, 100.01)
sum:126.05000000000001offby:7.949999999999989new best
(13.02, 16.08, 100.01)
sum:129.11offby:4.889999999999986new best
(16.08, 16.08, 100.01)
sum:132.17000000000002offby:1.829999999999984new best
(44.63, 44.63, 44.63)
sum:133.89000000000001offby:0.10999999999998522

best sum(44.63, 44.63, 44.63) = 133.89000000000001

Solution 2:

Took a break then went back to tackle this again. I have come up with a solution I believe to be much faster. Though it is still very very slow for large inputs and I have done no testing or calculations to support whether it is faster, I have not even tested it for correctness past two or three inputs. Posting it as a separate answer as it is a completely different method.

There is likely room to optimize specific functions in the program but the method is

initialization start by adding each number to its own solution. make an additional solution with no numbers and a sum = target + tolerance this servers as the initial score to beat if any input number is better than this save it as the current best solution add each number to a set of all sums achieved up to this point

iteration keep track of what the current size of the sums set is, if this set grows we arent finished looking for solutions make a temporary list for adding solutions, if we add directly to self.solution_list we add solutions to be checked in the current iteration, and we dont want this now we loop through each previously found solution in our list and check what happens when we add each number in the number list to it if the sum of the previously found solution and the current number is unique (not in sums set) and better than the previous solution we can add it to our temp list to update our solution list later and then update our set and best solution. note that we also check if that solution is worse than the previous solution, the only way this happens is when we overshoot the target by further than the previous solution was close to the target, for example if the previous solution had a sum of 5 for a target of 6 and the current number to add is 3 adding three brings us to 8 which is a worse solution and no adding of positive numbers will make it better now if the solution that we checked did not have any numbers that could be added to get closer to the target we dont have to check that solution anymore, its a dead end, so we can take it out of our solution list. We dont need to take it out of sums though or remove it from best sol if its there. similarly if the solution we checked added every number then accessing this solution in the future makes no sense as adding values would result in values already in sums. therefore once again we can remove these most solutions will be pruned out when all possibilities of adding numbers result in paths that have already been discovered at the end we can check add the temp list to the permanent list and check if anything was added so sums to determine if we are finished. If the temp add list is empty the program should also be finished.

It might be a bit hard to understand, let me know if you have any problems but I hope this helps you out :)

classsolution:

    def__init__(self, numbers, n_sum):
        self.numbers = numbers
        self.n_sum = n_sum

    defgetNumbers(self):
        return self.numbers

    defgetSum(self):
        return self.n_sum

classsolutions:

    def__init__(self, numbers, target, tolerance):
        self.numbers = numbers
        self.target = target

        self.solution_list = [solution([num], num) for num in numbers]
        self.best_sol = solution([None], target + tolerance)

        for sol in self.solution_list:
            ifabs(sol.n_sum - target) < abs(self.best_sol.n_sum - target):
                self.best_sol = sol

        self.sums = set(numbers)

    defiterate(self):
        sums_len = len(self.sums)
        add_sols = []
        for sol in self.solution_list:
            # if all get added to current sol then current sol will be obsolete# if none get added to current sol then current sol is a dead end# if either of these cases are true at the end we can remove this path# (leaving it as best solution if it is)
            added_all = True
            added_none = Truefor num in self.numbers:
                new_sum = sol.getSum() + num
                # if new sum is better that sol sum and not in all sums# it is a new solutionif new_sum notin self.sums andabs(self.target - new_sum) < abs(self.target - sol.getSum()):
                    added_none = False
                    new_sol = solution(sol.getNumbers() + [num], new_sum)
                    # update the best solution if new sol is betterifabs(self.target - new_sum) < abs(self.target - self.best_sol.n_sum):
                        self.best_sol = new_sol
                    # update sums
                    self.sums.add(new_sum)
                    # add the new solution to a list to add at the end
                    add_sols.append(new_sol)
                else:
                    added_all = False# prune redundant branchesif added_all or added_none:
                self.solution_list.remove(sol)
        # add the solutions
        self.solution_list += add_sols
        # return true when finishediflen(self.sums) == sums_len:
            returnFalsereturnTrue

target = 130
numbers = [13.02, 16.08, 100.01, 44.63]
solutions = solutions(numbers, target, 0.1)

i = 0while(solutions.iterate()):
    print(i)
    i+=1print(solutions.best_sol.numbers)

Output for 0.1 tolerance and target 134

01234567891011121314
[None]

Output for 0.5 tolerance and target 134

01234567891011121314
[13.02, 13.02, 13.02, 13.02, 13.02, 13.02, 13.02, 13.02, 13.02, 13.02]

for tolerance 0.5 and target 1340

012
.
.
.
134
[13.02, 13.02, 13.02, 13.02, 13.02, 13.02, 44.63, 13.02, 13.02, 13.02, 13.02, 13.02, 13.02, 13.02, 13.02, 44.63, 13.02, 13.02, 44.63, 44.63, 44.63, 44.63, 44.63, 44.63, 44.63, 44.63, 44.63, 44.63, 44.63, 44.63, 44.63, 44.63, 44.63, 44.63, 44.63, 13.02, 13.02, 13.02, 100.01, 100.01, 44.63]