Maximal subset sum smaller than a given value

Question

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.

What are the constraints on the array elements and the array size? — Raziman T V, Jan 22 '17 at 18:14
Elements are positive integers smaller than 10000. The array size is smaller than 1000 — guser, Jan 22 '17 at 20:05

David Eisenstat · Accepted Answer · 2021-03-02T13:13:03.077

1

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)

edited Mar 02 '21 at 13:13

answered Jan 22 '17 at 17:48

David Eisenstat

64,237
7
60
120

Would it be better to do `sums.update({sum_ + elem for sum_ in sums if sum_ + elem < k})`; `return max(sums)`? That would result in fewer additions to `sums`. Also, `max(sums)` might be O(1). – mwfearnley Jun 07 '20 at 14:16
@mwfearnley Sure, why not? Feel free to edit that in. – David Eisenstat Jun 08 '20 at 15:30
This algorithm has a worst case time and space complexity of O(2^n) where n is the length of the array. – Tom Mar 02 '21 at 12:18
@Tom only if you ignore the problem constraints and the revision that mwfearnley suggested. – David Eisenstat Mar 02 '21 at 13:13

score 0 · Answer 2 · answered Mar 02 '21 at 12:27

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).

Maximal subset sum smaller than a given value

2 Answers2