CODEWITHSUNDEEP
algorithm
khasquakhas
khasquakhas

Reputation: 21

Maximum Sum for Subarray with fixed cutoff

I have a list of integers, and I need to find a way to get the maximum sum of a subset of them, adding elements to the total until the sum is equal to (or greater than) a fixed cutoff. I know this seems similar to the knapsack, but I was unsure whether it was equivalent.

Sorting the array and adding the maximum element until sum <= cutoff does not work. Observe the following list:

list = [6, 5, 4, 4, 4, 3, 2, 2, 1]
cutoff = 15

For this list, doing it the naive way results in a sum of 15, which is very sub-optimal. As far as I can see, the maximum you could arrive at using this list is 20, by adding 4 + 4 + 4 + 2 + 6. If this is just a different version of knapsack, I can just implement a knapsack solution, as I probably have small enough lists to get away with this, but I'd prefer to do something more efficient.

Upvotes: 1

Views: 129

Answers (1)

btilly
btilly

Reputation: 46507

First of all in any sum, you won't have produced a worse result by adding the largest element last. So there is no harm in assuming that the elements are sorted from smallest to largest as a first step.

And now you use a dynamic programming approach similar to the usual subset sum.

def best_cutoff_sum (cutoff, elements):
    elements = sorted(elements)
    sums = {0: None}
    for e in elements:
        next_sums = {}
        for v, path in sums.iteritems():
            next_sums[v] = path
            if v < cutoff:
                next_sums[v + e] = [e, path]
        sums = next_sums
    best = max(sums.keys())
    return (best, sums[best])

print(best_cutoff_sum(15, [6, 5, 4, 4, 4, 3, 2, 2, 1]))

With a little work you can turn the path from the nested array it currently is to whatever format you want.

If your list of non-negative elements has n elements, your cutoff is c and your maximum value is v, then this algorithm will take time O(n * (k + v))

Upvotes: 1

Related Questions