I want to find the elements in a given positive integer array such that their sum is less than or equal to a given value T. When it is less than T it has to be the closest to the value of T. I hope this a variation of the subset-sum problem in dynamic programming.
For example, I have an array A = [1, 5, 9, 11, 15] and T = 18 The answer will be element 0, 1 and 3. That is 1 + 5 + 11 = 17
You can solve this in O(NS), where S is the sum of all elements in a fairly straightforward manner. While the subset-sum problem is NP-Complete, you can cache each sum you make (so you don't calculate repeated sums) for a pseudo-polynomial time solution. A simple python implementation as follows. This will return the minimum sum possible:
def solve(arr, T):
# the size of this set is bounded by S
possible_sums = set()
for i in arr:
# incorporate sums from adding i to each already seen subset
possible_sums |= {i + s for s in possible_sums}
# just i is an additional possible subset
possible_sums.add(i)
# return the greatest <= T
return max(s for s in possible_sums if s <= T)
Note that this will throw an error if all elements in arr are greater than T, so you just have to implement some edge case checking if that's a possible input.
Actually returning the elements in that subset gets a bit trickier, but not by much. You just have to create some link structures that let you backtrace.
def solve(arr, T):
# dictionary in the form of sum: last_index_added
possible_sums = {}
records = []
# do the same as before but remember the last index
for i in range(len(arr)):
possible_sums = {**possible_sums, **{arr[i] + s: i for s in possible_sums}}
possible_sums[arr[i]] = i
records.append(possible_sums)
# find the best sum and retrace our steps on how we got here
best_sum = max(s for s in possible_sums if s <= T)
record_idx = len(arr) - 1
res = []
while best_sum:
last_idx = records[record_idx][best_sum]
res.append(last_idx)
best_sum -= arr[last_idx]
record_idx = last_idx - 1
return res
Test case:
>>> print(solve([1, 5, 9, 11, 15], 18))
[3, 1, 0]
