Algorithm for finding a combination of integers exceeding a given value

Question

I am trying to develop an algorithm that will take an input array and return an array such that the integers contained inside are a combination of integers with the smallest sum exceeding a given value (limited by a combination of size k).

For example, if I have an array [1,4,5,10,17,34], and I specified the minimum amount of 31, the function will return [1,4,10,17]. Or, if I wanted it to be limited to a maximum size of array 2, it would just return [34].

Is there an effective way to do this? Any help would be appreciated!

Answer 1

Something like that? It returns a value, but can be easily adapted to return a sequence.

Algorithm: assuming the input is sorted, check the k-length combinations for the smallest amount greater than min, stop after the first element of the array is greater than min.

JavaScript:

var roses = [1,4,5,10,17,34] function f(index,current,k,best,min,K) { if (roses.length == index) return best for (var i = index; i < roses.length; i++) { var candidate = current + roses[i] if (candidate == min + 1) return candidate if (candidate > min) best = best < 0 ? candidate : Math.min(best,candidate) if (roses[i] > min) break if (k + 1 < K) { var nextCandidate = f(i + 1,candidate,k + 1,best,min,K) if (nextCandidate > min) best = best < 0 ? nextCandidate : Math.min(best,nextCandidate) if (best == min + 1) return best } } return best } 

Output:

 console.log(f(0,0,0,-1,31,3)) 32 console.log(f(0,0,0,-1,31,2)) 34 

Answer 2

It is rather a hybrid solution with dynamic programming and backtracking. We can use Back Tracking only to solve this problem, but then we must do an exhaustive search (2 ^ N) to find a solution. The DP part optimizes the search space in reverse tracking.

 import sys from collections import OrderedDict MinimumSum = 31 MaxArraySize = 4 InputData = sorted([1,4,5,10,17,34]) # Input part is over Target = MinimumSum + 1 Previous, Current = OrderedDict({0:0}), OrderedDict({0:0}) for Number in InputData: for CurrentNumber, Count in Previous.items(): if Number + CurrentNumber in Current: Current[Number + CurrentNumber] = min(Current[Number + CurrentNumber], Count + 1) else: Current[Number + CurrentNumber] = Count + 1 Previous = Current.copy() FoundSolution = False for Number, Count in Previous.items(): if (Number >= Target and Count < MaxArraySize): MaxArraySize = Count Target = Number FoundSolution = True break if not FoundSolution: print "Not possible" sys.exit(0) else: print Target, MaxArraySize FoundSolution = False Solution = [] def Backtrack(CurrentIndex, Sum, MaxArraySizeUsed): global FoundSolution if (MaxArraySizeUsed <= MaxArraySize and Sum == Target): FoundSolution = True return if (CurrentIndex == len(InputData) or MaxArraySizeUsed > MaxArraySize or Sum > Target): return for i in range(CurrentIndex, len(InputData)): Backtrack(i + 1, Sum, MaxArraySizeUsed) if (FoundSolution): return Backtrack(i + 1, Sum + InputData[i], MaxArraySizeUsed + 1) if (FoundSolution): Solution.append(InputData[i]) return Backtrack(0, 0, 0) print sorted(Solution) 

Note. . In accordance with the examples you specified in the question, the minimum amount and maximum size of the array are strictly larger and smaller than the specified values, respectively.

For this entry

 MinimumSum = 31 MaxArraySize = 4 InputData = sorted([1,4,5,10,17,34]) 

Exit

 [5, 10, 17] 

where as, for this entry

 MinimumSum = 31 MaxArraySize = 3 InputData = sorted([1,4,5,10,17,34]) 

Exit

 [34] 

Explanation

 Target = MinimumSum + 1 Previous, Current = OrderedDict({0:0}), OrderedDict({0:0}) for Number in InputData: for CurrentNumber, Count in Previous.items(): if Number + CurrentNumber in Current: Current[Number + CurrentNumber] = min(Current[Number + CurrentNumber], Count + 1) else: Current[Number + CurrentNumber] = Count + 1 Previous = Current.copy() 

This part of the program finds the minimum number of numbers from the input data necessary so that the sum of numbers from 1 to the maximum possible number (which is the sum of all input data). This is a solution for dynamic programming, for a backpack problem. You can read about it online.

 FoundSolution = False for Number, Count in Previous.items(): if (Number >= Target and Count < MaxArraySize): MaxArraySize = Count Target = Number FoundSolution = True break if not FoundSolution: print "Not possible" sys.exit(0) else: print Target, MaxArraySize 

This part of the program finds a Target value that matches the MaxArraySize criteria.

 def Backtrack(CurrentIndex, Sum, MaxArraySizeUsed): global FoundSolution if (MaxArraySizeUsed <= MaxArraySize and Sum == Target): FoundSolution = True return if (CurrentIndex == len(InputData) or MaxArraySizeUsed > MaxArraySize or Sum > Target): return for i in range(CurrentIndex, len(InputData)): Backtrack(i + 1, Sum, MaxArraySizeUsed) if (FoundSolution): return Backtrack(i + 1, Sum + InputData[i], MaxArraySizeUsed + 1) if (FoundSolution): Solution.append(InputData[i]) return Backtrack(0, 0, 0) 

Now that we know that a solution exists, we want to recreate the solution. Here we use the backtracking technique. You can easily find many good lessons about this also on the Internet.