Maximum Sum for Subarray with fixed cutoff

Question

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.

This is not exactly the same as the general-case knapsack problem, because (in knapsack-problem terms) you know that in your problem, each element's weight is equal to its value. However, your problem is still NP-hard, because it solves the subset sum problem. So you're not going to find anything much more efficient. — ruakh
– ruakh, Commented Jun 24, 2019 at 16:51
I think the description is unclear a bit. Do you want the subset with total sum greater than or equal to cutoff but with the minimum number of elements? — Ameer Jewdaki
– Ameer Jewdaki, Commented Jun 24, 2019 at 18:24
No. I can use as many elements as needed, but you can only add elements until the total is equal to or greater than the cutoff. So, by adding 4, 4, 4, and 2 it gets you to 14, but we're still under 15, so we can add the largest available element, 6. — khasquakhas
– khasquakhas, Commented Jun 24, 2019 at 18:45

btilly · Accepted Answer · 2019-06-24 18:50:59Z

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

Collectives™ on Stack Overflow

Maximum Sum for Subarray with fixed cutoff

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related