CODEWITHSUNDEEP
arraysalgorithmsubsetdynamic-programming
guser
guser

Reputation: 296

Maximal subset sum smaller than a given value

You are given an array of integers and a number k. The question is to find a subset such that the sum is maximal and smaller than given number k. I feel like there is a dynamic programming approach to solve this but I am not sure how to solve this problem efficiently.

Upvotes: 2

Views: 2191

Answers (2)

David Eisenstat
David Eisenstat

Reputation: 65458

The simple dynamic programs for this class of problems all use the same basic trick: for each successive prefix of the array, compute the set of its subset sums, depending on the fact that, when the input elements are bounded, this set has many fewer than 2^n elements (for the problem in question, less than 10,000,000 instead of 2^1000). This particular problem, in Python:

def maxsubsetsumlt(array, k):
    sums = {0}
    for elem in array:
        sums.update({sum_ + elem for sum_ in sums if sum_ + elem < k})
    return max(sums)

Upvotes: 1

Tom
Tom

Reputation: 1468

This could be done using the Subset Sum algorithm with a small adaptation. Instead of returning the boolean value from the last (bottom right) cell you search for the first cell with a value of true which indicates that there is a combination of elements that sum up to this particular k_i < k. This k_i is your maximal sum smaller than k. This algorithm has a worst case time and space complexity of O(nk).

Upvotes: 0

Related Questions