Algorithm for finding a combination of integers greater than a specified value

Question

I've been trying to develop an algorithm that would take an input array and return an array such that the integers contained within are the combination of integers with the smallest sum greater than a specified value (limited to a combination of size k).

For instance, if I have the array [1,4,5,10,17,34] and I specified a minimum sum of 31, the function would return [1,4,10,17]. Or, if I wanted it limited to a max array size of 2, it would just return [34].

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

Answer 1

Something like this? It returns the value, but could easily be adapted to return the sequence.

Algorithm: assuming sorted input, test the k-length combinations for the smallest sum greater than min, stop after the first array element 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

This is more of a hybrid solution, with Dynamic Programming and Back Tracking. We can use Back Tracking alone to solve this problem, but then we have to do exhaustive searching (2^N) to find the solution. The DP part optimizes the search space in Back 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: As per the examples given by you in the question, Minimum sum and Maximum Array Size are strictly greater and lesser than the values specified, respectively.

For this input

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

Output is

[5, 10, 17]

where as, for this input

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

Output is

[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, required to make the sum of numbers from 1 to the maximum possible number (which is the sum of all the input data). Its a dynamic programming solution, for knapsack problem. You can read about that in the internet.

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 the Target value which 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 the solution exists, we want to recreate the solution. We use backtracking technique here. You can easily find lot of good tutorials about this also in the internet.