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.
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)
Collected from the Internet
Please contact [email protected] to delete if infringement.
Comments